Ooh, sounds good to me! As for specific classes, I think the Bard would be your best bet: he’s handsome, suave, persuasive, witty, and generally the faceman of the group. In practice, bards combine magical spells and ability-boosting (or enemy-weakening) songs with combat ability. Alternatively, if you’re looking for someone with more combat ability the Rogue, who’s really sneaky, has a lot of specialized skills, and helps in combat by sneaking up behind peeps and stabbing or shooting 'em while the rest of the party keeps them busy. Finally, if you want to be the tough, devil-may-care frontman who singlehandedly clubs a bunch of unwitting enemies to death with a variety of sharp and pointy implements, you’re looking for the Fighter. He doesn’t have a particularly wide range of skills to chose from, but he’s one of the best pure combat classes.
If it were me, I’d lean towards the Bard or Rogue, since we’re emphasizing problem-solving and exploration over combat, and we don’t want you getting bored… but if a fighter feels more like what you’d like, we can definitely make sure he has lots to do. 
As for our setting: I don’t know how our other contributors feel about themes, but I was thinking that a late medieval theme with a slight bias towards steampunk might be a good start. What follows is a brief blurb about D&D settings… experienced players, feel free to jump in and correct me, because this is the first time I’ve used pure D&D in a bit; most of my campaigns in the last two years have been with a homebrewed system.
Anyway, down to business: Most basic D&D materials use a “stock medieval” setting that combines generic fantasy elements with weapons and armor of an indeterminate era. From there, you add on homemade or storebought materials to further tailor your world. Sometimes, if the aim is to have a historical campaign, things are very accurate: anachronistic elements are trimmed out, and all of your equipment is typical of what would be found in the time and place your game takes place in. D&D is extremely good at allowing this, so you can basically run anything from a stone-age game to something that takes place in the modern era. Other games, however, won’t tend towards the historical, and players tend to ignore (or, as is vastly more common, make good-natured fun of) the anachronisms.
For our specific game (and this is subject to change, in case anyone thinks of something cooler) I’m thinking a late, highly anachronistic medieval world with a European feel would be great: all kinds of melee weapons, fairly advanced bows and crossbows, and even elementary (and extremely dangerous to the user) firearms. As the game progresses, we can introduce new themes as they see fit: running through a mad scientist’s lair and stealing his stuff would give the party access to more futuristic equipment, while getting hired by cave-dwellers who have a firm taboo against technology might motivate the party into using less advanced means and methods.
)
