Yes, without a course in digital logic/design a CS major will not be able to do well with HDL at all. You don't necessarily have to know how to design an IC at the transistor level, but you sure a shit need to know the boolean algebra to be able to multiplex, decode, encode, create registers, etc. and most importantly the graph theory for state machines.
I'm not sure I'd agree with that. When you design using HDL, you're describing the behaviour of the finished design in terms of what you want it to do. The synthesis tool might infer the need for multiplexers and D-types, but that's not the way the designer has to think. We're a level abstracted.
For example, suppose you're writing an SPI slave, which needs to be able to return one of a number of different values depending on which address is being read. If you're well versed in fundamental digital building blocks, then you might start thinking about how this would be realised using multiplexers and latches. It's fine to be aware, at a very general level, that these are the components which will be required, but you don't need to actually work out how to implement your desired logic using them.
Your code might look something like this:
IF sclk'event AND sclk = '1' THEN
IF reset_n = '0' THEN
spi_result <= 0;
ELSE
CASE spi_addr IS
WHEN 0 =>
spi_result <= version_register;
WHEN 1 =>
spi_result <= bytes_remaining;
WHEN 2 =>
spi_result <= irq_outstanding;
irq_clear_sig <= NOT irq_clear_ack;
counter <= 0;
WHEN 3 =>
spi_result <= measured_value (counter);
counter <= counter + 1;
WHEN 4 =>
counter <= spi_written_value;
END CASE;
END IF;
END IF;
In this example, reading different register addresses should return different values, so clearly a multiplexer is required. Some values stored in latches are also clearly going to be needed.
But: there's quite a bit more to it than that. Reading the interrupt flag at address 2 also has the effect of clearing the flag and resetting a counter, so the design also requires a comparator and some reset logic for the counter. The counter also increments every time a result is read, so we need an adder, and it can also be directly updated by writing another register address.
Trying to work out the underlying building blocks required to implement this rapidly gets out of hand, but thankfully that's the job of the synthesis tool. I only need to be vaguely aware that X number of bits need to be preserved from one clock to the next, so I can estimate the logic usage of the design - and only then if it's big enough compared to the capacity of the chip for that to even possibly be an issue.
When I created a 64 bit processor on my FPGA, I described each and every one of those IC he has on that board and described how to wire them together using HDL. The HDL then interpreted what I described, synthesized it, and wired the transistors of the FPGA to create those IC and connections that it interpreted.
Oh, my. I do hope that something has got lost in translation somewhere, because describing individual discrete ICs (ie. standard, low level logic functions) and then joining them up is a terrible, terrible way to program an FPGA. HDL allows us to describe what we actually want a device to do, not how we think the thing we want could be built up out of basic logic elements.