Generally speaking, I would not use and HDR map as background. Use them only for reflection. Even the most hi-res of images tend to look crap as backgrounds because they're blown up so much.
I'm rendering 1920x1080 images with HDR envmap as background, and it looks sharp! You just need a very high resolution envmap. Best is to do it yourself with a SLR, but some very high res images can be found on the internet.
For instance, if you make outdoor animations or stereo images (like I do) , there is virtually no other choice than using the envmap background, because good parallax is almost impossible to match by compositing, and it looks fake.