So we've discussed this in the past and my notion was for a small sized ship. Something under the 200 range (not above). We've not always had the best track record with 4 ships running and I think right now, and as a way to "ease into it", we should do something that can support a smaller roster of say "10ish" rather than "15ish". Would never want to see it dip below 8 APCs.
Yes, I know you can technically run the biggest ship with the biggest crew with 5 people if you wanted but we've kind of established the paradigm of "like 15 players crew a ship of 300-1,000".
With that in mind, the classes I'd suggest are the following:
Saber (or similar fighter), Defiant, Daedalus, or an Oberth
Baring that, if we want or feel the need to go with an average size ship I'd like to make the following suggestions:
A Non-Federation Ship: Imagine it- a commandeered vessel, the ship of some defectors, or even a ship given to the Federation by an ally (or an ally faction within enema ranks). It could be like a bird of prey (Klingon or Romulan) or something far more bizarre. The crew would have the challenge of deciphering a non-standard (and oddly alien) ship's controls and systems, have all sorts of gremlins jump out at the worst time, some fantastic plot opportunities, and a VERY unique environment to roleplay in.
A Medical Ship: I would LOVE a ship that wasn't a big, bad, battleship. Armed with minimal weapons the crew would have to respond to threats like epidemics, deliver supplies to a far outpost, talk their way out of threats, use the ages of "We are a medical ship" to disarm situations, etc.
An Old Ship: The Federation NEEDS ships so they stop some relic from being mothballed and toss it on the front line. It's old, it's classic, and it's got some very retro controls. I'm talking like a TOS Constitution class, or something equally as old. It's clunky, it's got an overhaul but every nut and bolt in her whines when you pass warp 5, stuff doesn't always work right, you have to fight to the best. It's limits make the brave crew that man's her all the more gallant for the things they overcome.
Something on the Extreme End of the Spectrum: I'm talking some weird stuff. Either big as a sun and ugly like a Jupiter class, a time ship (I know... I know...), a Promethus or something like that.
Now these are some pretty extreme suggestions... why? Well a ship's class is largely interchangeable and cosmetic unless its something extreme. You can do a Galaxy class or a Sovereign class or whatnot... but it doesn't change the kinds of stories you tell. I'd argue that the differences between way of a Federation crew piloting a Bird of Prey vs a Galaxy class is much larger than the differences between a Galaxy and an Ambassador.
Basically- boldly go where no site has gone before.