When I started learning FPGA design, I first learned VHDL. I liked the language and used it exclusively in my designs... until I found about Verilog. Verilog made more sens for me because of my C programming background. But I also benefited from my experience with VHDL.
I think that you should learn Verilog and VHDL but start with Verilog. Verilog is less verbose and easier to grasp than VHDL. In addition to that, Verilog is very used in industry (in the US and major European countries) while VHDL is particularly popular in the academic circles.
"The following is not for the weak of heart or Fundamentalists." -- Dave Barry