api rate limiting: per user, per ip, or something else?

Hey everyone, I'm trying to figure out the best way to do API rate limiting. We're rolling out a new public API soon, and we really need to stop people from messing with our backend services. Should we go with limits per user (which means we need authentication), limits per IP address (but that gets complicated with NAT and proxies), or maybe a mix of both? What's actually worked well for you all, especially if your API handles both logged-in and anonymous users?