Verizon's service supposedly offers speeds comparable to a low-end DSL package. I don't have the service, so I don't know for certain.
I have Cingular with GPRS/EDGE service. It's certainly not as blazingly fast as my 8mbps cable internet in my home, but it's pretty fast. Faster than any dialup I've ever used. I'd compare it to an ISDN connection, if you can remember that far back.