King's Bounty and Starflight are excellent, but more rpg-ish than true rpgs for sure.
The Faery Tale Adventure, effeminate as it sounds, is an obscure one that I had some fun with. Warsong is an rpg more centered on combat but still fun, and an old favorite of mine is Gemfire, which really is more about military strategy but it's totally set in a world of wizards, monsters and the like. Check 'em out, you may have missed them.
Oh yeah, and D&D: warriors of Eternal Sun.
Sorry that some of these are only slightly RPGs, somewhat more adventure games, but it's slim pickin's on the Genesis. STill, I'm sure you'll like at least ONE of them.