Aside from that, I'm curious how do you manage alowing API clients to create new relationships or change them?
What's hard to understand? If you add a resource then you update your link relations. If you actually tried to implement a REST API instead of RPC-over-HTTP then the client navigates link relations just as before. That's pretty much the whole basic premise of REST.