After playing around: the XP changes introduced in the latest patch- challenging has become a cakewalk for me difficulty-wise. (I always play on challenging because I hate cheating AI's one way or the other, and I also believe it's the difficulty the game is intended to be played at)
Challenging has never been challenging in FE, at least yet. Try a harder level, and be sure to crank up the difficulty level of the AI players. Try for denser monsters, too.
I think weaker heroes make for a tougher game. Right now it's too easy to get a steamroller. It also devalues the late-game hero recruiting techs.
I've never gotten an extremely valuable hero without having the appropriate magic tech that allow me to grab level 9 champions, first. So I'm not quite sure what you mean. By the time you acquire that tech, you should be far enough along that such champions fit into your armies.
Also, I think the game needs to spawn some random heroes over time , as too many of them are killed quickly.
But they can't be killed. They come back with various penalties. (Unless you're referring to stationary encampments of as-yet unaligned champions. And that really doesn't fit your argument.)
Each to their own, but I like the sparse sprinkling of champions across the landscape. Aside from your leader, they're the most valuable units you've got. Getting too many of these would be a cakewalk. Still, if you want more, just take the Betrayers trait. Then you can hire on champions from both the kingdoms and the empires.