Adding bevels to a simple object messes up the mesh
Thanks to the help from @cgslav, pointing me in the right direction, and from this video: Blender Hard Surface Modeling : Are NGons Bad?, I was able to work out the steps to get the bevels I wanted without the messed up final result. Those steps are as follows:


First, add the bevel to the bottom four edges to convert those
angles to smooth curves.
Now you can add the finishing bevels to the straight edges:
Go into Object mode
Click Smooth in Tool shelf -> Tools -> Edit -> Shading
In Properties Editor -> Data -> Normals, select Auto Smooth
Go into Edit mode
Make sure select mode is set to Edge Select
Press A to deselect all edges
Menu Select -> Sharp edges
Properties -> Transform -> Edges Data
Set Mean Bevel Weight to 1.0
Set Mean Crease to 1.0
Press Ctrl-E, select Edge Data -> Mark Sharp
Press Ctrl-E, select Edge Data -> Mark Seam
Go into Object mode
In Properties Editor -> Modifiers, select Add Modifier -> Bevel
Under Limit Method, choose Weight
Increase number of segments to 4
Set Width to 0.1


Here is the final result:



As you see, the side surface is perfectly flat and straight now. I am very pleased with this, and hope it will help others who come across this same issue.