Put each request in a queue, process N requests a second and tell people how many people are in front of them/how long it will be. Adjust the N requests per second based on how much you want to spend max

Maybe something like this: save prior responses and let anyone see those, only requiring an account to ask for new ones.

Rate limit it by ip address (and/or combination of other request/header data), and be transparent about the limits. Have a blurb asking users not to abuse it by keeping requests to a minimum. Captcha every nth request. I could go on.

Why do you want to limit free uses? Is it because it costs you money, or because you think there's a product worth paying for here?

You need more strategic thinking: if you get so many people trying to use this thing that you can't afford you bills you have an excellent problem with a million solutions

My first thought was this must be a joke if you expect me to login to use it

With IP addresses or cookies.

OAuth could make the signup process simpler.