I have used these before. They're about $70 in single quantities and have an extensive feature set: they support everything from PPP to http and ftp and are pretty easy to use. I think they offer Arduino sample code, but not sure.
The module is about 1.25" square and has pins on (IIRC) a 0.1" spacing.