Not all Ukrainians have accents. Some of them can be easily confused with Russians.

The most prominent part of a typical Ukrainian accent is more breathy "г". This is not a 100% accurate way to discern a Ukrainian, because some people from the South regions of Russia pronounce "г" the same way. But in 99% of cases it's a dead giveaway, along with some Ukrainian or semi-Ukrainian words that bleed into Ukrainians speech (like "шо" instead of "что"). Other mentioned traits are relatively rare.

All in all, I would not say that Ukrainians have strong accents (comparing to other foreigners), because most sounds in Ukrainian are identical to those in Russian, and 1-2 sounds that are pronounced slightly differently do not make for a "strong" accent, in my opinion.