I usually gravitate to the more simpler characters not because my excecution sucks but because i don't like spending lots of time perfecting certain movements/combos when i can simply play. Haven't played much of the older fighting games, so i can't really comment on that. Anyway i'll list a few character that i played and personally think are pretty excecution heavy.
SSFIV - Ibuki, superjumpcancels and one frame links,
SCIV - Setsuka, those just frames
TTT2 - Steve, learning his duckcancel combos is pretty frustrating but needed