Some of these ideas sound a bit like putting more shoujo in just for the hell of it.
Anyway I think you got the difficulty spot on in the last one.
Maybe a Sporty Shoujo skill, like the ninja or android, that makes the shojo run everywhere ahead of the others instead of walk.
An idea found in the original Lemmings games that might be quite interesting to apply was using the same level 2 different ways.
Like in the easier stages say you're on a high platform, and a load of androids to reach the goal at the bottom. Simple.
But then in the later levels you're put back on the level but minus the androids. I seem to remember that coming up quite a bit in one of the Lemmings games I played.
Also on the Lemmings theme if you wanted to be kind you could put in something like the Sand Pourer. So many times when I was playing through it my Shoujos were barred from getting anywhere because there was a tiny little barrier or lump in the way after making a way to somewhere. 1 out of 6 times I might have be able to remedy it with a damn archer, but mostly I just made it worse
Having to restart the whole level that you've managed to do right this time because of 2/3 pixels got really annoying in places (read mostly Fantasy)
Oh, and another thing as well (I can't stop now I've started!

) Most of the latter levels struck me as being either Up or Down levels. In up levels you got a load of building or creating shoujo, painters/flower growers etc to help you go upwards, adding new terrain
In Down levels you got a load of destructive shoujo, Bratty, Devil etc to help you go downwards, through terrain. In Sexy 5 it really struck me though, that there were no 'creative' Down shoujo, like a downwards painter or a lift operator Shojo (

). And like in Sexy 5 when there wasn't a lot of land to destroy to go downwards, one would have been useful. Similarly there were no 'destructive' Up Shoujo, like I dunno a Human Cannonball Shoujo that makes a upwards diagonal passage through blocks of terrain. (I can only see a few sorts of places where this would be helpful though)
Phew, I said a lot more than I thought I had to say. And just for the record (you could probably get quite the wrong impression from ^^^) I did think Shoujo Attack was a great game
