Electro-Koopas are probably the most Mario-y thing, besides the staple characters themselves. I didn't mind them, since there have been electrical enemies in past games (Jelectro in SMB3, for instance).
What I hated was the Stus (the little creatures with mustaches that are all over the airstrip later). Where in the heck are the Goombas?!