I think you guys would do a fantastic cover of 'Journeyman' by Iron Maiden. If you made it a little heavier (only a little) and kept that acoustic, folky element to it, it'd be so damned good.
Ever since Mikko suggested to me to get Jethro Tull's Stormwatch, their song Kelpie has become a favorite song of mine. I would love to hear a Kiuas cover of this track. Just listen to that chorus!
I'd love to hear In the Hall of the Mountain King in the Kiuas Style. But for more contempory songs to cover could be The Trooper by Iron Maiden and/or Sympathy for the Devil by Rolling Stones .