"just isn't there a way to not have the texture distort? "
I am not sure. Perhaps you scale them to a standard size in photoshop, but don't constrain the proportion when you do it. That way, you will have them saved distorted but when you apply them to an odd shape they will appear normal.
I don't think there is a push button method to make them perfect without any forthought, although it might be a nice plugin to scale projections.
As far as using odd size images. It takes the same memory to hold a 513x513 image as it does a 1024x1024 because of the format that maya uses to store the information. Or at least I think it does. So don't worry about scaling an image that is 500x800 to 512x1024. It is good practice to keep your image dimensions powers of 2 (ie. 2, 4, 8, 16, 32, 64, 128, 256, ...)
ww