The flavors of Virginias are very subtle, like flavors of tea... very subtle, and requires you to smoke very slowly to get the most flavor.
This is exactly right. You can compare some categories of tobacco to food parallels pretty simply -- eg. latakia to smoked meats / jerky -- but VAs are complex and subtle, and sometimes defy neat food comparisons. Cosmic's illustration (not parallel, but illustration) of tea is perfect.
(On second thought, one of the great VAs could be not only illustrated by tea, but actually paralleled to it -- Capstan Blue. It does have a sweet iced tea sort of taste.)
And what Cosmic said about the careful technique required to taste VAs is spot on. If you draw like you would on other tobaccos, you'll just taste acrid ash and wonder why others love VAs.
And red Virginias are completely different - more like dried fruit
Yes, different sub-genres of VA have different and typical notes -- yellows CAN taste cigarette-y if you're not extra careful, but with age and technique, they can taste like sweet hay/silage. Reds can have notes of dried fruit, dough, toasted sweet breads, etc. And so forth.
My favorites include HH Pure VA (probably my pick if I had to choose just one), Union Square (can be inconsistent... a little age helps... but when it's good, it's good), and Capstan Blue (which has a tangy, and as I said sweet-tea like character).
A couple others were mentioned which, while great, may not be what to cut your teeth on --
Newminster 400 is delicious, but it does have a caramel topping which may give you the wrong impression of straight VA.
And Orlik Golden Sliced is one of the best things I've ever smoked
once it has a decade on it, but fresh it isn't nearly as good. More importantly, it's got a lovely apricot topping which may likewise get in the way of getting a feel for straight VA.
If you're new, you may shelve VAs a while. Many of us smoked latakia for years before VAs opened up to us.
Enjoy!