Heck, the same way Horde already get to the Gnomeregan pet dungeon; teleport straight to an NPC that will queue you up, no special entrance necessary.
A Stockades scenario could be interesting. Horde players fall into the shadowy figures’ trap, getting captured by the guards in Stormwind, and must pet battle to escape while Alliance players get framed and must acquire exculpatory evidence.
Mortimer Moloch, having assumed his twin brother Randolph’s identity following the riot he led, keeps his fellow inmates pacified under the condition that pet battling is tolerated as a prison sport. This pet trade kingpin and undefeated pet battling champion has pets smuggled in for those without collections of their own in the hopes of finding a worthy adversary.
I think the Stockades could easily be made as diverse as the Deadmines: rats, cockroaches, canal crabs, spiders, ghosts, prison food leftovers, offspring of Stormwind’s Sewer Beast, earth and fire elementals, Riverpaw gnoll runts, and unique pets used by the prison’s pet battle champions with one of Mortimer’s serving as the first time completion reward.