Your best bet is probably to crop the photos when printing, especially if you are unfamiliar with editing photos on your PC. Most of the photo terminals at supermarkets I've seen have had the ability to let you rotate and crop photos.

You will lose resolution when doing this, to avoid pixelation when printing you really need 300ppi (pixels per inch) for a reasonable viewing distance you can get away with 200 or 150 absolute minimum. At 200ppi you could print your images 10"x7.5" whereas cropped to portrait that goes down to 7.5"x5.75"

Assuming the images were sharp to begin with you should be able to get away with printing them 7x5.

The only thing you need to do to preserve quality when rotating and cropping is to save the images back using the highest possible JPEG quality setting (as JPEG is a "lossy" format you lose data every time you save) or use a lossless format like PNG, TIFF (some labs wont support these however). That's one advantage of doing the rotation/crop yourself, as you have full control unlike the machine at the lab.