how about somewhat proggy folky metal with death/black/power metal thrown in? Moonsorrow. Orchestral... not really, but melodic with mouth harps, fiddles, etc folk instruments & 8-30 min per song, mostly about iron age pagan tribe's battles, lore and life. All of the songs in finnish tho, so some language barrier.
Other than that, I'd probably go with Avantasia, Rhapsody, and such. Can't beat the classics :)