I am a New Zealand Passport holder and my spouse is a UK passport holder. We have just moved to Spain where she has found work as have I but I am waiting through the very hard process to get my work permit and residency. Is there a way I can get it through her? Even if it's via marriage.
In this situation, you are indeed entitled to residence card as family member of an EU citizen, which should generally be easier to obtain than a residence permit for work. It's definitely the case if you are married or in some form of registered civil partnership, possibly also if you can simply prove that you have a long-term relationship.
For more details you can look at previous questions covering these aspects of EU law with respect to other countries (but the rules are supposed to be the same everywhere), e.g. Can a non-EU citizen with a EU partner live and work in the EU?, Moving to Frankfurt with my Swedish wife, I am not EU citizen, What is the process of getting a UK visa and a work permit for a non-EU citizen married to an EU citizen? or US Citizen with EU Spouse who doesn't yet have a job.