Hearthpwn

If you wanna try some forfun/casual lists, I'd recommend Cho and Gazlowe. If you want competitive, then go for Neptulon and Bolvar. Toshley can be a thing too, but the most appealing ones for sure are the two class legendaries. 

Go for Dr.Boom man.

Actually I was referring to Zoolock man, sorry. Handlock may be a strong archetype but Zoo is simply too cheap.

You can say the idea isn't new and there were some attempts before, but being able to competitively play mill in Hearthstone is the new thing for sure. 

It's good another archetype seeing some hype every now and then besides Huntards and Cancerlocks.

Keep Baron man. Although uncontested a Warrior card, you can fit him in other classes too if you simply want to wreck aggro matches.

Lol, the op made a thread complaining about one of the most unusual archetypes to ever see play in Hearthstone, like Mill Druid is some kind of Cancer Zoo/Huntard deck. 

Sure, people are on the hype wagon but the ideia itself is very original and a new approach to control-ish decks. And soon enough the number of netdeckers will set down a bit since the Mill archetype only shines higher on ladder.

In the current meta Jones has as much value as Black Knight, you should consider craft him eventually. 

You seem to have all the current most competitive legendaries already besides Harrison Jones, now it's time for pick some other fun niche legendaries: 

Sneed Old Shredder - seeing some play in Druid Ramp and as a generic late game threat for more controlish archetypes;

Blingtron 3000 - has been used in Amaz' Priest, but as far as I remember it screwed him more often than not, can combo with Harrison Jones; 

Malygos - once I get all the competitive legends in the game (I'm missing 1 or 2) it'll be my first forfun legendary to craft, one of the most stylish finishers!; 

Gaslowe - another fun legendary to build a list around it, goes well with Toshley;

Mimiron's Head - you said you don't like Rogue, but this guy may be actually tricky in some comboish list;

Lorewalker Cho - you already has Mukla, why not try some funny mill deck ?! 

Thalnos can be replaced in budget lists like you already mentioned, but you can fit him in many classes: Rogue, Mage and Shaman are the classes where it shines the most, but it fits in Druid quite well also. So, almost half of the classes in the game can make good usage of him. 

On the other hand, Gallywix and Cleef are too niche cards. Miracle isn't doing so well as in last season due to Auctioner's and Leeroy's nerf, and even when it was a dominant archetype Cleef wasn't a must.

Gallywix seems fun and underrated (I'm playtesting it and he usually gives me more value than the hyped Troggzor), but I'd wait a bit for crafting him. 

If you like Rogue so much then it may be better to wait for now, if anything the class has a good aggro in the form of Backspace which gets eclipsed only due to Zoolock's and Hunterattle's popularity, but is extremely effective for laddering and farming as well. Once the meta estabilizes you may ask again which legendary is the best pick for another archetypes of the class. 

 Jaraxxus is a must in Handlock lists, but the class has another very popular and competitive archetype in the form of Zoolock;

 Cenarius although playable in virtually any Druid list isn't a must in any of them; 

 On the other hand, both Grommash and Tirion are must in the only competitive archetypes from their respective classes, while also playable in mostly of the tier 2/forfun lists as well. 

 In my opinion Grommash and Tirion belong to Ragnaros and Sylvanas tier (maybe Cairne as well ?!), while Cenarius and Jaraxxus belong to Harrison and Black Knight tier. 

Don't know if Cenarius and Jaraxxus are ranked as high as the other class legendaries you mentioned.

You can DE both Velen and Millhouse without much remorse. Then you almost have dust for another legendary, but I'd think twice wether disenchant Malygos. Never DE your Ysera man, although there are some better choices right now in the meta Ysera always see some play in control archetypes. 

Sylvanas and Ragnaros are the best neutral choices, only once you get both I'd recommend other good circumstantial neutrals such as Black Knight and Harrison Jones. Thalnos is an excellent neutral as well but it's more of a supporting minion, it can be replaced by either Kobold or Hoarder in budget lists. 

If you decide by either Warrior or Paladin I'd also recommend Tirion or Grommash before any legendary not named Sylvanas or Ragnaros. 

If you play Paladin properly then by turn 5 you can have 4+/7 Bolvar easily (except for the top deck scenario of course). With the rising of Muster for Battle and Quartermaster people tend to spend resources removing Silver Hand Recruits, making Bolvar a strong turn 5 play or an overwhelming late game finisher. 

People get punished for overlooking the SHR, by either Quartermaster or Equality shenanigans. With Bolvar they also get punished for constantly cleaning the board. It's not a top tier legendary, but fills the empty drop 5 spot in any Paladin list nicely and is flexible enough to be a later game play as well. 

I'm no pro-player, but having some experience in TCGs and making some research I believe that Bolvar is currently the third most played class legendary from GvG - behind solely Neptulon and Vol'jin. It's ironic cause people were hating on him way more than other class legendaries which aren't seeing as much play in competitive lists such as Iron Juggernaut, Gahz'rilla or Malorne. 

agreed.

No way man. With such a card then Flame Leviathan would become too broken, since Control/Freeze Mage would always draw him with the spell. It would be a spell which gives you a free Consecrate plus a War Golem to your hand. 

I opened a FL last week and currently can't test him, but I'll find some room for the guy in my Freezing Mage list and see how it gets. Like I mentioned before with the draw engine of Freeze archetype we may increase the chances of getting it on the critical turns we'd need him - making the awkward Ice Block scenario less likely as well.