First step -- don't use Internet Explorer.

In fact, when I try it, it seems to completely ignore my paper/orientation choices.

If it's XP, then the built-in picture viewer...

In fact, the built-in Photo Printing Wizard (which comes up when you press Print from the viewer) just seems to do the "right thing". It's pretty cool.