That which starts with many polys will tend to end with many polys. The problem is getting a start with all of those polys...

Subdivision can work, but there's definately an art. And some programs are better at it than others. I don't know how well Blender does subdivision because I've never had the patience to get a grip on that seemingly sinister UI. The only reason I've had to actually play with Blender to date is getting models out of PCS2 to AC3D.
AC3D will subdivide any unlocked model on-screen, I believe. Thus, if you don't want something that way, you disable it in the heirarchy. Committing a subdivision will create the smoothed-out mesh. From that point, you'd drag the desired verticies into the proper position to finalize the form, blah, blah, blah.
However, because subdivision is often a pain-in-the-backside to use, why not try playing directly with verticies? What I typically do is select an edge of the surface and insert verticies along that edge. I might make a similar set of verts on the other side of the surface I'm trying to smooth. Then, I'll slice the surface (thus creating more polygons) until I've got the number of polys I'll need to do the job. Lastly, I'll pull that higher-poly mesh into form, getting the desired curvature. And that's only one way... And probably a hard one. You'd do something like that for detail modeling, imaginably.