Some of the career institutes offer Paramedic programs, but the quality of instruction may vary wildly, from what I know of them from Florida I cannot really recommend one unless your boyfriend is incredibly self-motivated and capable of teaching himself the material.
My advice would be have him talk to some members of DC Fire Rescue and find out where they went to medic school and where they would recommend he go.
If he's already a certified Basic or Intermediate he should find out if that group offers Paramedic level training. Also, be aware that if he's coming with a certification from another state, there's a chance that Maryland/Virginia won't accept his current certification and he might have to start training all over again from the Basic level.