Aha! Figured it out.
Permissions were wonky on my .htaccess file. Once I set them correctly and WP could re-write as needed, stuff worked normally.
Anyone have any ideas? Even when my site is under very low load, the CPU usage jumps to 100% within seconds of me changing my permalink structure.
Anyone have any further information on this? I’m struggling with this as well for a few of my plugins.