Since a data plan costs me extra and I don't really need that I haven't booked it for years.
AGPS via wifi works fine, but I've never seen it working via cell towers. Depending on how many satellites I see it does sometimes take 5 minutes to get a fix.

Whether navigation works without a data connection depends on the application you use. My experiences so far:

Navit: purely vector based and has its own routing algorithm.
So once you've downloaded the data for your area (e.g. the Germany data has about 2GB) you're fully independent. The lack of raster data might be a problem though, if you're used to orientation by topography.

Modrana: uses raster data and has its own routing algorithm as well as online routing.
So you should download the raster tiles in advance. Both algorithms seem to work equally well. My main gripe is, that you can't change routing tracks by hand, e.g. because you know the suggested route isn't optimal.

Marble: uses raster data and online routing.
Unfortunately the Marble version on the N900 is very old and the routing API has changed since then. So it can't find tracks on its own anymore, but you can still import tracks from a more recent Marble version and routing with it works fine. Alternatively you can use a more recent Marble version via Easy Debian, but that comes at the cost of a cumbersome UI because it's not optimized for a 3.5" single-touch screen.

Mappero: I haven't used this in years, so this is just namedropping for reference.
I don't even know if it still works. I think it was raster data and online routing but my memory might trick me. Basically it had nothing for me that Marble didn't have.

I prefer Marble, because despite its shortcomings, as a cyclist I heavily rely on manual track adjustment and topography.
I must say though, that I still prefer paper maps. So I rarely navigate via smartphone. For me it's basically just a stopgap, which might make me unusually willing to compromise.