How can I get some nice eye candy themes for Grub?

There still are not too many themes for Grub that are are easy to install. The process of theming Grub is quite complicated. There is a guide available here: A Beginner's Guide to Theming GRUB2

Though that includes a 37 page PDF document to read through! A simple but effective way of sprucing up Grub is to add a custom background image. The easiest way I've found of adding one to Grub is to use Grub Customizer

To install this enter these commands in a Terminal:

sudo add-apt-repository ppa:danielrichter2007/grub-customizer
sudo apt-get update
sudo apt-get install grub-customizer

Then run Grub Customizer, when it has loaded click the Preferences button and then the Appearance tab.

See image below for newer version of Grub Customizer.

Then select the file icon under background image and navigate to your chosen image file (I found that selecting one of the default wallpapers looks effective, I'm using the new Pangolin image from the 12.04 wallpapers). You can also change the font colour of the menu at this point (useful if your background image colour makes the text unreadable - a preview will appear when you select a background image to check whether you'll have any colour clashes).

Then close the preferences pop-up and select the Save button on the main screen, then you can reboot your system to admire your handiwork!

Here is a tutorial from "UpUbuntu" to change Grub 2 background image in a few simple steps

When you start your system, a boot menu will show up containing an ordered list of operating systems and kernels. This boot menu is black by default and can be customized as follows:

Start the Ubuntu terminal and install first the grub2-splashimages package with this command:

sudo apt-get install grub2-splashimages

GRUB spalsh images are stored in the /usr/share/images/grub folder, you can access it with this command:

sudo nautilus /usr/share/images/grub

If you want to use a custom image, make sure it is in the TGA format, then place it in that folder. After deciding which image to use as splash screen for the GRUB2 boot loader, edit now the /etc/default/grub file with this command:

sudo gedit /etc/default/grub

At the end of the file, add this line:

GRUB_BACKGROUND=/usr/share/images/grub/YOUR-IMAGE.tga

Replace YOUR-IMAGE.tga with your custom image name.

When you finish, press CTRL+Q and save your file. Run now this command:

sudo update-grub

Restart now your computer to see if changes are successful (hold down the SHIFT key to bring up the GRUB boot screen while rebooting).

Here is a manual how to install burg manager, a graphical front-end to configure burg, a graphical grub-manager. It even has a emulator, so you can directly see how your boot-menu will look like.

1. Just be careful when using it with other tweaks like grub resolution changes (altough it worked for me).
   
2. Also watch out for special boot parameters (like acpi=off) - burg will not automatically copy them from your /etc/default/grub file, you will have to do that yourself (to /etc/default/burg).
   
3. I'm also not shure how burg will behave if Ubuntu updates your kernel, maybe it will overwrite burg.