Orange pekoe does not actually have orange in it. See this article:
http://en.wikipedia.org/wiki/Orange_pekoe
I, too, am a tea purist. I usually drink my tea without any sweetener or milk or cream, and I prefer loose leaves over teabags.
A good place to find loose-leaf tea is an Asian food store. This is actually how I became interested in tea.
Some recommendations:
Sencha - This is a common Japanese green tea. It has a very pleasant flavour. Good Japanese restaurants often order this stuff straight from Japan, because it's even better when it's fresh (produced no more than six months ago).
Genmaicha - This is sencha mixed with roasted rice. I think it's a good tea to try for someone who thinks they don't like green tea.
Matcha - This is green tea ground into a fine powder. Mixed only with water, some people may find its flavour unpleasant, but it actually goes quite well with sweetener and/or cream.
Pu erh - It is always described as having an "earthy" flavour. This is actually quite literal--it tastes like dirt. It's a worth a try just to experience it, even if it turns out you don't like it. Sometimes it tastes better on the second steeping. Also, unlike other teas, it gets better with age.
Gunpowder green tea - This tea is rolled into little balls, giving it the appearance of gunpowder. It has a stronger flavour than other green teas--one that I would describe as somewhat "smokey".