As I recall, both Quake and Marathon defaulted to arrow keys for movement. Half-Life was the first time I encountered WASD out-of-the-box.

> (Or should my games have used hjkl)?

I still play a game that does...