Ok, I knew there was a reason I haven't used a modem in 8 years. There's nothing like connectiing at 12kbps on a 56K modem, the busy signals, and disconnects galore.
Here's the solution I ended up with, eventually.
Sanyo 8100 Sprint PCS Vision Phone
Phone to USB Cable
Sprint PCS with Unlimited Vision plan
Dial #777 with PPP and PCS Vision Modem script
about 14k/s of downloads on a 230,400bps connection. Not too bad and there's no dialup ISP required. DNS server not provided, use your home internet connection for that if needed.