I agree that Nebulas (which are as much as 90% the size of a Galaxy-class) would rate a CAPT or at least a senior CMDR; according to navy.mil CMDRs and CAPTs may command bases on shore (the closest RW equivalent to a starbase) although this becomes less teniable as tensions with the Cardassians, Klingons and Dominion mount as the series goes on (ADM Ross or his predecessor really should have been installed no later than s4); I agree that a CAPT was overkill for the Defiant, but looking outside the USN, LCDRs are tasked as COs for crews as small as 20-25 if a degree of autonomy is desirable (the RANs' Fremantle and Armidale-class patrol boats for instance); again, I agree that Janeway's rank should have been CMDR (unless we suppose two ranks of CAPT), especially as her XOs were LCDRs.
The Galaxy-class is typically assumed to have a crew of around 1,000 (roughly inline with the old Invincible-class light carriers of the Royal Navy) or the San Antonio-class LPDs, however this is not inconsistent with the idea of the CO being a CAPT (as CVNs often have at least three, if not four or five CAPTs embarked (CO, XO, CHENG, CAG, Flag COS), especially as Yesterday's Enterprise indicates that the Galaxy-class has a capacity of seven to eight thousand and Ensigns of Command suggests a short-term evac capacity of up to fifteen thousand. As noted above, CDR would be sufficient for Intrepids (and indeed the earlier Constitutions) and LCDRs for Defiants , Oberths and Sabres, though in all cases they could hold the title of "Captain" ("Skipper" or "CO" are also acceptable internationally if preferred).