I recently purchased a large fixer upper with a 135 gallon AO smith gas water heater built in 2001. Only two people are living in the house so we need a fraction of that amount.
A larger tank does not cost more energy. The only thing that costs energy is when the water cools - and that depends only on the surface area, not the amount of water in the tank. (Mathematically volume increases by the 3rd power, but surface area only by the 2nd power.)
So to save energy add extra insulation around the tank. Reducing the amount of water in the tank will do nothing since it won't save all that much surface area (and potentially none at all).
(Yes, it takes more energy to heat the water in the first place, but after that it doesn't matter - and you already heated it.)
Actually, the math seems to contradict parts of the top-voted, accepted answer.
Assume that you decide to cut the volume of the water tank in half, by reducing, in proportion, the dimensions of the actual internal tank, while leaving the shape the same, and leaving the thickness of the insulation the same.
This would require each linear dimension to be reduces to 79.4% of the original value (cube root of 0.5).
This in turn means that the any area of the tank would decrease to 63.0% of the original volume (79.4% squared). So, theoretically, this reduced tank would have heat conduction losses reduced to the same 63.0% of original.
This said, there is no real-world way to achieve this reduced size without replacing the tank. As others have pointed out, reducing the water temperature and adding insulation are both cost-effective ways to reduce stand-by costs
Water tanks store the water under pressure, just like the rest of the piping in your house, so there's no way to keep it partially full. Turning down the temperature would be a great way to save money if it's higher than the recommended 120º.
If you can't or won't turn it down, you might just consider replacing the tank. 13 years is getting up there for a hot water heater... you might only have a few more years left in it. Plus a new one is likely to be more efficient, regardless of size.
Turns out, the surprising answer is you can reduce the thermal energy stored in a fixed size tank water heater.
At rest, water in a tank stratifies or even 'stacks', an effect well known to solar installers. Hot water floats up top and cold water sinks.
A typical older water heater has just one temperature sensor low down in the tank. Move that sensor higher on the tank, and it won't react to cold water at the bottom of the tank. The top of the tank will have hot water, the bottom cold water, pretty much like you wanted.
Now there is a significant downside: vigorous flow can mix the water in the tank, giving you the average between the hot water on top and the cold water in the bottom. If you could carefully draw the water off the top there would be no problem, but cheap tanks are going to introduce some turbulence and run the stratification pretty quickly.
And note this works better in electric heaters compared to gas heaters (with an electric you can disable the lower element, and regardless there is less mixing with the heat is on).
Great discussions on these matters can be read in United States Patent #6880493 or http://www.greenbuildingadvisor.com/blogs/dept/musings/all-about-water-heaters