Turns out it was actually related to the anti-forgery token. I'm using Angular so I'm setting my headers manually in my Angular service rather than using the built-in ServicesFramework setModuleHeaders method and was only setting the TabId and ModuleId. I didn't think the [AllowAnonymous] attribute would override the anti-forgery stuff but it looks like it definitely does (which is good to know).
Full solution for those doing the same:
var baseUrl = sf.getServiceRoot('[yourmodulename]') + '[controller]';
var config = {
headers: {
'ModuleId': sf.getModuleId(),
'TabId': sf.getTabId(),
'RequestVerificationToken': sf.getAntiForgeryValue()
}
};