You can't get round the geometry. Your DSLR takes pictures in the aspect ratio (the length of the long side to the length of the short side) of 3:2. Most compacts, as well as some manufacturer's DSLRs and quite a bit of medium format gear (anything described as 645) is in the aspect ratio of 4:3. Other medium format gear is 6 x 6 - so the aspect ratio here is 1:1 (one advantage of this is that you can defer the portrait versus landscape decision for prints - it's rare to make square prints, even when working with 6 x 6 images).
Meanwhile, the 'traditional' photo paper sizes are all over the place - we have 6 x 4 (3:2, which is 1.5 to 1), 7 x 5 (7:5, which is 1.4 to 1), 10 x 8 (5:4, which is 1.25 to 1) and so on. A series paper, which is common in Europe, is sqrt(2):1 (approximately 1.41 to 1). "Letter" sized paper is 11 x 8.5 - approximately 1.29 to 1.
You have to crop your image to suit the aspect ratio you need in the final output - if you're printing with borders, take the borders into account. Letter with a half inch border all around will have an image size of 10 x 7.5, which is 4:3.
This means you might have to make allowances when composing if you know you're likely to want an image at a particular size. For example, when I was composing some group shots that I knew were likely to be printed on A series or 7 x 5 paper, I left a bit of room at the left and right of my image so that I could crop from the left and right to get from the 1.5:1 of the camera to the 1.4:1 (or thereabouts) of the output.
Particularly on medium format gear, it's not unknown to have aspect ratio markings in the viewfinder. Indeed, you can get suitably marked focus screens for some higher end Canon DSLRs, but they're not used that commonly.
It is the aspect ratio that matters when cropping. Because A4 is in the same aspect ratio as A3, I can take an image I cropped for A4, and print on an A3 using the same crop - assuming that I'm working borderless on both sizes (as I said earlier, you take the borders into account when working with aspect ratios). A4 with 50mm borders all around is not in the same aspect ration as A3 with 50mm borders all around.
Canon compact users have the opposite problem - their cameras are 4:3, so if they want to print 6 x 4, they have to crop a bit off the short edge. In other words, you need to make an allowance at the top and/or bottom of the frame if shooting with a Canon compact and wanting to print on 6 x 4. Some online printers offer 6 x 4.5 prints to get round this - but they don't fit in many albums.
The only other way to avoid cropping is to scale the image unequally - so you might slightly compress the image from left to right to get a 3:2 image on 7 x 5 paper. Don't do it - it looks absolutely horrid.
Sometimes a creative crop can really improve the image. I use a technique based on the rectangle tool and paths to store multiple crops in Photoshop CS3 files (which I have mentioned before in these forums), or different crops in virtual copies in Lightroom.
David