As long as you stick to the 16:10 and 16:9 aspect ratio's, it can be resized properly for almost everyone.
I don't know which size your original tends to be, but if you start at 2560x1600 you've got all the 16:10 resolutions covered. Find a nice cropping, and you've got the 16:9 ones.

I myself would really love a 32:10 wallpaper, as I'm using dual monitors, but hey - that's a pretty exclusive wish, which is of no use to most people.