Verilog gives you enough rope to easily hang yourself.
VHDL gives you so little rope you'll want to hang yourself.
As a vehicle for teaching H/W design though, I think VHDL would be better. It's much more explicit and rules oriented, and looks like you're describing H/W. Once you've learned VHDL, picking up Verilog is fairly trivial. I would think going in the other direction would be a bit harder.
Language Bias Disclaimer: I've been using VHDL for 10 years, and Verilog for 2...