Hey Rodeo, (love the name btw)
As a fellow TT gamer, as well as a RPG gamer of 20+ years, I kinda see where you are coming from, though I do have few caveats to address before I can say I agree with you fully..
Try running gaunts etc in Hordes before completely deciding they are underpowered. Remember to use the +damage according to magnitude, as well as any special rules they might have (swift attacks, lightning attacks, weapon qualities etc). Also keep in mind that horde damages hit *everyone* and they can't dodge or parry in most circumstances. I think you'll see regular 'troops' become much more deadly. This seems to me that it mirrors the TT though does lean towards the more cinematic experience that most RPGs strive for (and that the fluff engenders).
Elites *are* pretty scary. My group slaughtered several gaunt hordes in one of my recent games, but once 5 warriors showed up we had to get smart in how we tackled them. The GM ran them smart as well, and we ended up taking a couple casualties before we defeated the encounter. Note I said 'encounter', we actually were pressed to kill all of them, and eventually completed our objective and got out of there. (mainly because we knew from earlier experience that to stay in one place is to invite more and more bugs, and *that* is not a good thing.)
Master level creatures are actually very deadly, especially when used in combination with their minions (elites and troops). We engaged a baseline Tyrant in the mission, and he and his Tyrant Guard messed us up. We were able to defeat him, but lost two marines in the fight, as well as almost failed our primary because the Tyrant was smart and almost killed the VIP we were sent to rescue. Again, we had to engage him in a limited amount of time, and just barely escaped before the Lictors, Genestealers and Gaunts washed over the area.
I realize that other creatures are outside the scope of your original post, but if you really want to challenge your players throw some CSM at them. Outfit them like Traitor marines (autocannons, heavy bolters, power swords, Emperor forbid, CHAOS Termies) and give them the same squad tactic rules that we have. If you *really* want to be evil give them a Chaos Mark (the Nurgle mark and Khorne marks are especially sick). In one encounter with a CSM squad (that vaguely mirrored our squad) they successfully ambushed our Librarian and Devestator (and rghtly so, they are the biggest threats in our squad). They popped them both in a single round which obviously put the rest of our squad at a severe disadvantage. Again, we were able to overcome them, but only due to a liberal use of Fate points and thinking outside the box. I admit, I'm not looking forward to facing the Tzeentch Sorceror that he teased us with last week, he's going to be painful.
I guess my point is kind of what AK-73 said, use the book as a guideline, but go off the reservation a bit if you need to. Buff them up, throw huge hordes at them, do what you have to in order to make them respect your encounters.
I remember that you said you didn't want to outright kill your players, just challenge them and you know, now I think about it, the badguys may not be so underpowered so much as hard to balance a tough versus easy encounter as written in the book. In my groups experience, our GM is definately not afraid to push us with numbers and encounters balanced towards 'hard', but it did take us several missions to get to the point where things felt balanced in difficulty for our team.
Anyway, just a few thoughts. Much luck with getting things worked out.
-Bell