Okay, so, here's a sort of tutorial-in-a-model for a couple of things:
(I'll do a tutorial or quicktip in the Thingiverse Blog later on modifiers in general and subsurface modeling in particular.)
The critter here was created by taking the default cube and using the Modifier tab: add Modifier: Subsurf. Clicking the little circle whose tooltip reads "apply modifier to editing cage during edit mode" will give you the awesome function of having the edges of the mesh seem to curve around the smoothed-out mesh.
The result is a ball in edit mode made of six squarish patches. You can extrude these like faces and Blender will show you this soft, organic-looking mesh that is way more intuitive than strict polygons. The critter was made doing nothing more than extruding this funny soft mesh around.
I've included the Blender file of this stage in the modeling so you can go to edit mode yourself and see how a completed mesh can have hundreds of faces in the final product but only a few dozen in the underlying "control cage".
To get to an STL file though, I'm pretty sure you have to apply all mesh modifiers so click "apply" on the modifier window from object mode. Now your mesh is just a mesh, but a much more complex one than the one you started with.
To smooth off the feet in this case I just dragged in a cube, scaled it so it intersected the bottom of the model about where I'd want the build plane to intersect, and booleaned the two meshes. In object mode, this is select first mesh, shift-select second mesh, w-key and select "difference". Depending on which you select first this'll either generate a mesh that's the cube with footprints in it or a critter with the bottom cut off. (I think you select the critter first to get what I've done here.)
I also have included the Blender file of the model after this. (Remember, Blender leaves the originals behind and in-place when you boolean, so don't assume you've failed just because you don't see any change! Drag the model to the side to see what you've created!)