Dipping into my book of The Horse, Russian breeds dating from the 18th century onwards include the Don (because used by the Don Cossacks) and the Orlov. Both of these are mixtures of other horses however. Far more ancient is the Akhal-Teke, known to be 2,500 years old. It is smaller than the other two and is almost hairless (no mane). It was used by the Mongols and Turkopoles.
The very best Russian cavalry horse was (is) the Budyonny, but it is a blend of other horse breeds and only dates from 1920.
Finally mention must be made of the small Mongolian wild horse (Przewalski's Horse) which is almost certainly the closest link to a prehistoric horse. It has been identified in cave paintings 15,000 years old. Aggressive in a group, it can of course interbreed with other horses. That is a long way from Ukraine though of course.
There are many Polish horse breeds in the book, too many to mention , and that is closer to Ukraine so some may have come from this direction? Hope this helps.
[edit] Looking again at the OP's question, I would say in general from the info above that the more East you go in Russia towards the Eurasian Steppe the smaller the horses might be?