Legends are still allowed in normal play, therefore from a strictly competitive standpoint they are no different from regular pokemon except maybe the IV restriction.
But you should be concentrating on countering, not just looking at the base stats. In DP, walls practically NEED resistances to be able to stand up to heavy hits. Choice Banded Heracross would down Skarmory, Hippowdon and a lot of physical walls which are neutral to Fighting and/or Bug, due to its immense power. Therefore, the safest option is to go for Gliscor, which resists Fighting and Bug, Heracross' other attacks are much less threatening. In fact, Heracross does not have a reliable physical Ice move to hit Gliscor with, so it would be walled indefinitely.
Since you're just starting, just go with a combination of three walls:
Cresselia, Gliscor, Blissey
They should cover almost everything.