But this is a design issue not a coding issue.
Anyway the problem with smooth rotation is that it requires a lot more art to be drawn.
Maybe you could sacrifice a little realism and get it animating smooth by scaling the characters over the horizontal axis, around their center, like 1.0 -> -1.0
Obviously they'll be paper thin at some point, but that would be very short. It could be the styleof the game. Paperthin layers. ;-)
- goes for 2D platformers.