They mean the same thing (big in size) . Both can also be used for "great" but there seems to be an unwritten rule about this. "Veliký" is used as "great" but only with people. Alexander the Great = Alexandr Veliký.
Velký is more often used as "great" with things but not necessarily exclusively. "He had a great influence" = On měl velký vliv. or On měl veliký vliv.
The historical figures seem to be the only case where VELIKÝ or VELIKÁ are used exclusively.