... and was even awarded a triumph for his efforts against the Lusitanians there, remember? That's when he had to choose between triumph and consulship.

Suetonius (I think it was him) claimed Caesar was quite aggressive during the propraetorship and harassed the Lusitanians until he had a war in his hands. The story goes he chased them from their mountain holds (not an easy task if you know the mountains) and all the way to the Atlantic ocean; they escaped to the nearby islands (Berlengas?) and he had to get ships brought from Gades (Cadiz) to pursue them. This may or not be true - the weather near the Berlengas islands is usually foul; on the other hand sailing up the western Portuguese coast is no meagre feat for ships coming from Cadiz, which would usually be battling the northwesterly winds...

Oh, and the first time he was in Hispania was when he was quaestor.