I been struggling with this same issue since day one. I too tried using the same Res wallpapers with the same issue lol. Soo I did some experimenting. For me what worked was a combination of two things. First off I use 1280x1024 wallpapers and I use quickpic to apply them. Here's some screenies to compare gallery and quickpic..
This image I'm sure ur familiar with. Nice n square and not cropped as we want it to be.
Here as you can see the crop toll within quickpic fits the rectangle horizontally quite perfectly and only cutting off the image at the top and the bottom. This is something that has become quite acceptable to me lol. Well I hope this helped
Sent from my GT-P3113 using Tapatalk 2
Samsung Galaxy Tab 2 7.0 - AOKP JB - 1.08Ghz/8gb + 16gb
Nexus S 4G - AOKP Build 38/Matr1x Kernel 19.5 - 1Ghz/16gb R.I.P 7-26-12
EVO Design 4G - [ICS 4.0.3.] Metallic Blue