Well for the timing, I also did nearly the same thing, The game started a year before, during the Klingon invasion of Cardassia.
Ship wise, you might also want to look at the Excelsior Era, Centaur class scout or the Galaxy Era, Freedom class scout. Stay away from the Nova's in any combat they're flying coffins with their write-up. Slow, weak shields and weapons.
I recommend Scouts because they have more leeway in how to accomplish their missions, and their not as overwhelmingly power as an Explorer. The smaller crews make for the PC's to find answers to problems rather than have a GM character hand it to them, also the concept behind them is speed and avoidance rather than head to head encounters. There by making things "More Quiet".
Also something to keep in mind, Dominion Shield technology. The Federation had little in the way of really affecting Dominion ships. I don't remember when the discovery was made off the top of my head, as to when they were able to deal with the Dominion as they would any other hostile species. Plus during roughly the same time Federation Shields were useless against the Dominion.
Phoenix...
"I'm not saying there should be capital punishment for stupidity,
but maybe we should just remove all the safety lables and let nature take it's course"
"A Place For Everything & Nothing In It's Place"