Vikings, definitely, it'd be pretty cool to see you just attack various civs on a whim, attack someone when you need the money, then get out. In addition, playing without diplomacy would be kinda interesting if you ask me.
I really think it would be interesting if the Vikings had a Boat UU that allowed them to travel several tiles out into the open ocean; not too far, but good enough to, as in the case of this map, be able to hop from England to Iceland to Greenland to Newfoundland (Vinland), as happened in reality (or so most historians allege) I'm sure that this kind of thing has already been debated in the past.