That means NO razor-sharp "thrashing" guitars, and ABSOLUTELY NO SHREDDING, but lots and LOTS of old school-sounding, galloping NWOBHM with understated, classical-sounding, and super-melodic and/or harmonized, mid-tempo soloing all over the place. In other words, music with a focus on super-melodic and moving solos in favor of needlessly-technical/fast ball-swinging shred BS.

Stuff less focused on Priest/Motorhead-like, rhythmic riffing/pounding drums/"attitude" too... Just not what I am looking for.
And, as mentioned before, really mildly-overdriven guitar solos, none of that "RAZORS EDGEEEEEEE" Thrash-heavy distortion/speed.

I want some music that is unpretentious enough that it's suitable for a pub, but emotive enough that it makes one feel like they are riding a fuckin' horse to slay a dragon or something...

I don't have enough of this kinda shit in my life, my experience being pretty much limited to vintage Iron Maiden...

I dunno how else to explain what I am looking for, to be honest... Not even really sure of an appropriate song example to explain what I mean...

Fates Warning (first two albums especially; Awaken the Guardian is just as excellent but might be too aggressive), Slough Feg (this album and Twilight of the Idols in particular; Traveller should musically work but it's a lot more "modern" and distorted than those two), Glacier (one of the most melodic demos I know of), and Omen (maybe a little more aggressive but certainly triumphant and melodic) will hopefully work for you.

Hm, I have a couple bands in mind, but neither of them fit ALL your criteria, but you could give them a shot anyways.

The first one is Warlord. A lot of their 80s material is quite melodic, definitely not thrashy. There are some shredding solos though. And I don't know if there's enough galloping, but you can try it anyway. Here are some songs to try out:

Warlord - Black Mass
Warlord - Lost and Lonely Days
Warlord - Penny For a Poor Man
Warlord - Aliens
Warlord - Soliloquy

Maybe an even better Warlord song would be the demo song they put out for their forthcoming album:

Night of the Fury


The next band is Lordian Guard, lead by the same guitarist as Warlord. I think this band more fits your criteria of having LOTS of melodic solos, while much of them harmonized, and not being thrashy. There is a little bit of shredding, but usually it's just small isolated patches in the middle of melodic solos.

HOWEVER, the area it might fail your criteria is the "pretentiousness." And being able to play it in a bar. The best way I can describe the music is epic and majestic. There's keyboards, and more than one song between their two albums has spoken word passages. But I guess you can give it a try if you feel like it.

Lordian Guard - War in Heaven
Lordian Guard - Winds of Thor

And here's a ballad with very melodic soloing, if that's okay:

Lordian Guard - My Name is Man

I hope this post is not useless and you find something you like!

Fates Warnng - Old FW is something I amazingly haven't heard yet... I have been a fan of (two songs of of) Parallels for years... the album as a whole kiond of thurns me off, because it sounds ike a Prog Metal band attempting Adult Ontemporary, especially with the super-synthetic (triggered?) drum sounds, complete with AC/R&B cliches like the synthetic "reverberated woodblock sound" (which I hate).... But I love the songs Eye To Eye and Don't Follow Me. I have listened to the later a kajillon times, actually, I just never much liked te rest of the album, but I do like the sound of this 80's stuff...

TLW Slough Feg - Really liked this, particularly the solos, which get fairly close to what I have in my head.

Glacier - Musically, this is not exactly wht I had in mind, but it's still really good. and the vocals aren't "not my bag" for the most part... Great instrumentation. I could see myself listening to more of this despite it being a bit more modern/"sharp" than what I was looking for.

OMEN! Whoa, I forgot all about this band... I actually really enjoyed this abum, but someow I completely lost it in the back of my subconcious. Really good, and actually not a bad suggestion for the thread, even if it s a bit fast-ish ad heavy. I am glad you reminded me of this album.

___________________________

Warlord - Yeah, definitely harsher guitars than I had in mind, but still an insteresting/likable sound.
Other than the guitar, it's kind of nicely "understated" without sounding too much like Foreigner, haha.

Lost And Lonely Days had some really nice moments


Probably not something I'd listen to a lot, but it isn't unenjoyable, regardless.

Lordian Guard's.... interesting.
I actually like the (to me) odd vocals, even if it isn't what I had in mind... Kinda makes me think of old, froofy, proggy/AOR music with strange vocalists like Pavlov's Dog.

Cool geetar stuff, and the solos are quite the sort I was hoping for, though maybe not "pedestrian" enough for my tastes (haha). The tone of them is pretty much spot-on though. I am not wild about sme of the the over-the-top synth in the songs, but the pace is ideal, as is the melodic guitar tone, as I mentioned.

I also like the bit at he end of the first track around 7:08+
3:55-ish in the econd track is a great example of the kind of melodiousness I am looking for in the solos as well.

And, as a side note, I love the dirty, saturated cassette-like production (seriously, that sounds like a rather lo-fi, standard cassette 4-track recording to my ears, and I mean this in a good way), especially on the solo synth strings (I know I mentioned I wasn't crazy about them, but they sound good solo on a raunchy tape, as does acoustic guitar).
___________________________

Thanks for all the recommendations so far.

Also, I should add that "isolated shredding" is fine, I was just trying to make sure to avoid bands that were nothing but, but a bit here and there is okay.

Parallels might as well be a completely different band, you really need to check out their first three albums. I'm not even sure where to start, but it is completely worth listening to the entire "Awaken the Guardian" album to properly introduce yourself to the band. The solos aren't as frequent as you might like, but the vocalist is amazing and very melodic, and the riffs should please you. The "prog metal attempting adult contemporary" feeling is a creative way of saying how I feel about Mark Zonder, the drummer that joined the band after their fourth album, "No Exit", and the vocalist of the first three albums, John Arch, is somewhat of a cult figure around here because he fucking rules.

Seriously, you will love this album. I think there's something in the terms and conditions of using Metal Archives that you are required to love John Arch*.
http://www.youtube.com/watch?v=OUJQ5Kngw8g

In addition to the entirety of ATG, listen to The Apparition and sing along.
http://www.youtube.com/watch?v=YmozVRLZfdg

I think you would like Shok Paris - classic heavy metal, the vocalist might be too much of the "attitude" that you don't want, but there are a few melodic, mid-paced solos.
First album: http://www.youtube.com/watch?v=cqHUfaL7Ftw
Second album: http://www.youtube.com/watch?v=tO5VIuVLUFU

I have a feeling that you probably already know Manilla Road.
http://www.youtube.com/watch?v=76rX8wVeVNo

*Not literally, but you should anyway.

I think Randy (Denmark) might be just what you're looking for, totally underrated band with a huge "lighter" NWOBHM influence (ironically, despite your post my first recommendation contains the lyrics "walking the razor's edge"):

http://www.youtube.com/watch?v=GoSuD6-dJa0

A few others that kind of fit this category:

Scamps (Sweden): http://www.youtube.com/watch?v=eFOX5N7zTTk

Amethyst (USA): http://www.youtube.com/watch?v=HP2Q6pR9h7k

Zeus (Spain): http://www.youtube.com/watch?v=Y6AueVYwD8s

And because its me, I'm obligated to recommend you a few ultra-obscure Japanese metal bands that I think may fit your inquiry Probably not the greatest to listen to in a bar, but I'm not one to care much what music I listen to around other people:

Legend: http://www.youtube.com/watch?v=9V8o5tJBsNo

十二単 (Juni Hitoe): http://www.youtube.com/watch?v=w7M1c-nVOSU

Precious: http://www.youtube.com/watch?v=LR0qC-3oBJ8

Actually, the "lighter" side of NWOBHM seems to fit this recommendation perfectly (if I am interpreting it correctly!) so here are a few favorites from the more obscure side of this scene. *Note: Some of these bands were deemed "not metal enough" for the archives. Not a complaint, as I respect the moderators' decisions, but you may have to look for information on some of these bands elsewhere.

Big Daisy: http://www.youtube.com/watch?v=df6yTiH2Vds

Apocalypse: http://www.youtube.com/watch?v=u-tGwjOL-Mc

Damascus: http://www.youtube.com/watch?v=IwYjdg1-aS4

Bitches Sin: http://www.youtube.com/watch?v=u5yRahSajM0

Crucifixion: http://www.youtube.com/watch?v=Wp7KVcdh4P8

Bleak House: http://www.youtube.com/watch?v=zowid7KAmnM

Jameson Raid: http://www.youtube.com/watch?v=lSFWb8hIu4s

Hopefully at least a few of these fit what you're looking for

If you've never checked out the NWOBHM Legend they might hold some appeal. Their debut came out in '81 but they sound "old" even for the time. There aren't a ton of songs that make you feel like you'll be charging into battle but they do slip in some pretty heavy riffs with a strong Sabbath influence. I think you'll definitely dig the soloing though, very tasteful and reserved, with great phrasing and tone.

Here's a randomly selected song from their second album, it's got a slow-build but I think the payoff is worth it: http://www.youtube.com/watch?v=-IRNWRSTKTE

Jonah Quizz are another band from way back in the day that kind of just got lost in the fold. They have a great mix of hard rocking riffs along with the occasional galloping. The solos are definitely full of harmonization and other classic NWOBHM fare (although these guys are actually Swedish). The lyrics are all in Swede but the guy has a really passionate delivery.

Random track from their Anthology compilation, very modest (pedestrian?) leads start up around the 3:30 mark: http://www.youtube.com/watch?v=ggJRQ5xAot4

I second the NWOBHM Legend (and the other NWOBHM Legend, and pretty much every other Legend. Its one of those band names you just can't go wrong with)

As stated, it might not be exactly what you're looking for, but its a great band and should not be overlooked.