Well, I tend to do the opposite. Whether in Gnome or KDE I put the menu bar at
the top just because I am contrary minded, I guess.

You can get themes for Gnome from art.gnome.org and gnome-look.org. If you add
KDE you can get even more customization and the menu bar is at the bottom by
default. It is more Windows-like by nature and has more features. If you stick
with Gnome you can add Emerald and get more themes that change your decorations,
but that means using Compiz which I do because I have loads of RAM and a 3D
graphics card. Any fairly new computer should be able to handle it. If you are
using something a few years old then stick with Gnome or KDE and customize it
instead of adding resource hogging features which is fun, but can be a
distraction.