Is there a way to smooth a surface cleanly without subsurf?
Try settings as follows:


One level of subsurf or as many as you can comfortably handle.
A Laplacian Smooth modifier with a couple of repeats (be careful!); adjust &lambda;factor as desired.
Smooth shading enabled.


The Laplacian Smooth modifier is a really nice way to smooth out your model without adding a ton of verts. From the wiki:


  The Laplacian Smooth and Shape Enhanced modifier allows you to reduce noise on a mesh's surface with minimal changes to its shape, and exaggerates a shape using a Laplacian smoothing modifier in the reverse direction using a single parameter, factor.


If this doesn't work out well you could try just a normal Smooth modifier instead.