Iirc (edit - apparently incorrect) Halo was the first to use left joystick as forward/backward and left/right strafe; and right joystick as look up/down and pivot left/right.
I even recall articles counting it as a point against the game due to its 'awkward controls' ...but apparently after a tiny learning curve, the entire community/industry got on board.
If we're talking Goldeneye, I believe the C-button aiming was an alternate control scheme. IIRC, the default controls had the stick control both your forward/backward motion, but also your left/right turning, instead of left/right strafing, so your aim was controlled horizontally by the stick, but vertically was pretty much locked on the horizon at all times. To do fine-tuned aiming, or to aim vertically at all, required holding R to bring up the crosshairs which you could then move with the stick, while standing still.
In hindsight, it's amazing that we ever tolerated that.
Metroid Prime used them too, and it worked fine. The game was designed around it, so enemies were either already on your level, or were slow enough to react that you could stop and aim.
The remake has other control schemes, but I don't use them because I like the one the game was made for.
You're correct. In addition you could strafe using left/right C buttons, and you could look up/down using up/down C buttons, but that was awkward and not really designed to aim.
But we also must remember that those games had an auto lock system. Your character would actually target the ennemies by himself, you would only use the crosshair to dona headshot when you have time to aim, or to aim at a specific object in the game.
But yeah, that seems so clunky compared to what we have today
Tbf it was always gonna be hard to make good fps controls on the N64 controller. The movement itself was fine once you got used to it (including strafing etc), but the real sticking point as you mentioned is the shoulder button aiming. It pretty much forced you to stop dead to aim accurately. So you really had to pick your time to hold position and take a few shots before running again.
I still had a lot of fun with it despite knowing there were better options out there with mouse and keyboard (although come to think of it when I was first playing wolfenstein and Doom I think I played with keyboard only back then).
Goldeneye scheme was forward and back on the joystick moved forward and back but left and right on the stick turned the camera in that direction. The opposite movements were on the c buttons (strafe left and right and look up and down).
It was incredibly disorientating going from that to Turok which used the strafe on the c buttons and looking on the stick. It's the same feeling I now get when I try to go back to Goldeneye now that the other orientation has been made universal.
On a side note, the goldeneye controls allowed for a unique way of moving around the map with circle strafing that you can't really replicate in other games.
Goldeneye got it functional, but it was janky. Try playing 4p with the old N64 controllers and you’d sorta struggle to move and aim.
Halo updated the standard with something usable in modern games. I think a few games in that genre also set the expectation that weapons should have no aim penalty while strafing, since console players would use small strafing motions to do light aim correction.