I've made a quick script that automatically chooses a 4:3, 5:4, or an 8:5 ratio wallpaper based on your /etc/X11/screen.conf.
This prevents wallpaper stretching, though your wallpaper will be needed to be saved in 3 formats (4:3, 5:4, and 8:5 ratios).

The script is here: http://dl.dropbox.com/u/758367/rezpick.sh

Installation Instructions

1: Make your 3 wallpapers and save it in /usr/share/images. Their default names in the script is 43_wallpaper.jpg (4:3 ratio), 54_wallpaper.jpg (5:4 ratio), and 85_wallpaper.jpg (8:5 ratio). Of course, you may change the script to match your filenames too.

2: Save the script somewhere (wherever you want it)

3: Set the script to be executable, and start it while you are logged in (this is _not_ a boot-up script, sorry).

4: Run the script, and it will choose a wallpaper that won't stretch or shrink on your screen (you may try this by making perfect-circle wallpapers)

Limitations

* This hasn't been set up to use Xorg (yet).

* The script can only choose the resolutions in it. While this isn't complex, it can't detect the display ratio if you have a wacky resolution.

Please try it, and improve it too (I know most of it can be done simpler, so...)!