Creating Base for non-flat surface
If your model has nice geometry around the edges, the first step should be a lot easier.
My answer is provided as an Imgur post (for some reason the steps are in a funny order, sorry) as I can't upload the gifs here - they're too big. I'll outline the basic steps though, just in case the link dies for any reason. All of the operations are performed in Edit mode.

Step 1: Select the vertices around the base of the mesh.
Step 2: Extrude the vertices down to whatever you want the depth to be along the z axis (E, Z, MOUSEMOVE). Then flatten them to a plane (S, Z, 0).
Step 3: Make a face by pressing F. You may want to recalculate normals at this point.