Actually, I've played FE 6 and it seems that that one was almost as easy as FE 8. I mean ****, theres like 7 arenas in the whole game. I remember trying to beat HHM without arena abusing, I got stopped at Cog of Destiny. However, I don't really play FE for the challenge anymore, I play for the supports.
Also, I'd recommend Radiant Dawn, it's the most challenging FE game on normal more alone, and if you can do hard mode on that game, it could probably go in the guiness book of world records. I myself like how the cutscenes look, it's such a unique graphical style. Also, that game had the best/difficult final boss fight I've ever done. But they really need to bring back the old support system. It gave me a reason to play the games over and over again. I mean really, look at all that you could learn about the characters in FE7, Bartre marries Karla? Priceless. In FE:RD the supports are the same for pretty much everyone, "Hey how ya doin?", "Fine, and you?" I was highly HIGHLY pissed that they took away the old support system. =(
Play Extraordinary Emblem Bros. Duel