Fail2ban rules like "after 5 failed logins, ban for 30min, 10 failed logins in a day (with no succesful login) is a permaban" will curtail most non-spear phishing attacks.
"I know I used my usual password, but did it start lower or upper case? Or camel case... did I end it with a number? Did the service require a special symbol, so I added that to the end? Or to the beginning.." - banned.
The reality is that, these days, I rent $5 worth of botnet time and make {user,password} combo login attempts from thousands of residential IP addresses.
You might think your advice is a good "might as well" elementary, but generally if people want to curl your /login page from their laptop, then they are also buying $5 scripts off Hack-Forums that automate botnet cred stuffing against your service as well. And you'll need a better gameplan than fail2ban.
Don't be a PITA to your users, and you've eliminated most of the "guess what password you used" game.
If a user fails credential checks (e.g. password), track it, if their current failure rate is N, tell them they tried too many wrong credentials, come back later. Every random(1,T) seconds any failed users get their failure count reduced by one until it's zero and you stop tracking it for now.
By choosing N and T you can give users a relatively large number of "goes" to remember their password after a long period away, but not give attackers too many chances to guess a not-awful password by brute force.
For example if N is 10 and T is 7200 then a user can try ten passwords, then an average of 24 more attempts per day but exactly when they can make another attempt is random. This allows your good guys to have a fair chance against any bad guys smashing the "retry" button to try to lock them out. If the bad guys give up and go away, the user quickly returns to having ten attempts.