My B&M guy hit me early with a tin of McClelland's Red and Black. It ripped out my tongue and drove me far away from Virginias. Besides the occasional Frog blend, I steer clear of McClelland's.
Soon after, I tried some OGS, which everyone raved about. I got little enjoyment from it and still pickled my tongue.
Then, I scored a bag of GH&Co Kendal North Star, a VaBur shag. Although a bit "plain", I was able to enjoy it and I began looking more closely at Virginia blends.
This was all early in my pipe days and certainly my technique was lacking. I moved into some PS Bullseye Flake. I enjoyed it and it was fresh. Everyone implied that it was much better with age, so I cellared a bunch.
Then, I scored some aged FVF and, along with some evolving technique, things began to click. Now, my first cellared batch of Bullseye is about 2 years old and I'm getting excited about digging some out.
These days, I enjoy the occasional VA flake and more than occasional VA blend.
I second the C&D Pegasus recommendation. If you find it to your liking, push your luck and get further down the rabbit hole. C&D Winchester is another candidate. Both cheap, available and forgiving.
Puff away on your burleys at work and save the VA's for the relaxed weekend affairs.