Hi Matt:
Don't know where you live, but I have successfully used Multitech embedded modems (
www.multitech.com). They have a whole selection of modems with different price/preformance (mostly speed) ratios. I typically use their 2400 Baud modem because it is cheap ($25 approx.), and I do not not need high speed anyway for my embedded applications.
Initialization is quite simple. Typically you just send a single initialization string consisting of some AT, &S, and &W commands.
Hope that helps!
Jem