But would a 100% deterministic game actually still be fun or interesting? What would a game like that even be like, can't think of any examples off the top of my head
A game I would consider to have very little "randomness" is Quake Live.
The only significant random element is the spawn locations. And even those are just semi-random as you can force your opponent to spawn on a "weaker" side of the map (spawns within a certain radius* of the living player are disabled). I can't think of anything except the spawns that are actually something random that the players have no control over.
*the radius is dynamic and changes size based on a few conditions, however it is not random, and people have it figured out to 100%
Whenever you talk about luck in QL 1v1, it's about how the players interact with each other. For example: "Player1 was lucky to survive that fight because Player2 ran out of Rocket launcher ammo" or "Player1 was lucky Player2 got fooled by that faked Rocket jump". These are not dice-roll situations though, it's not random, but it's still luck-ish (some pro-player will even attempt to track rocket launcher ammo of their opponent, if needed).
Again though, my opinion is just "less random is better" not "fuck all random elements".
Edit: and for the record, if it wasn't clear, I find QL very interesting to watch.