Begin teaching fundamentals much earlier. For me, I learnt Java classes and some fundamentals for it, but more basic programming skills went by the wayside until 2nd year of Uni.

The course we did on logic was good both years, but stuff like data structures and algorithms (sorting, linked lists etc) should be taught first.

Something else that might be useful is maybe not learning Java initially. What annoyed me with that (and I'm sure confused some people) was the amount of
- "Hey what does that mean?"
- "Uhh, don't worry about it yet"
which while it might encourage you to go read about it, is more likely to encourage the opposite, and tend to ask less questions, even when switching language.

I can't say for other universities, but I think a larger focus should be on gaining skills in the field, rather than becoming employable through doing employability things.
I know plenty of second year students that still couldn't have completed our first semester first year assignment, which was essentially some object manipulation wrapped up in a few classes and a basic console I/O.