There are various answers to this question depending on the level of autonomy of the client interacting with the service ...
Lets first look at a human driven client - the browser. The browser knows nothing about banks, concerts, cats and whatever else you find on the net - but it certainly knows how to render HTML. HTML is a media type with support for hypermedia (links and forms). In this case you have a perfectly working application with a client that only understands generic hypermedia. The "fixed interface" here is HTML.
Then we have the autonomous clients or "scripted" clients that are supposed to interact with a service without human interaction. This is probably the kind of client you are thinking of when comparing REST to SOA(P). You could find such clients in integration scenarios where two independent computer system exchange data in some predefined way.
Such autonomous clients must certainly agree on something in order to interact with each other. The question is what this "something" is or is not.
In a service oriented architecture the clients agree on specific URLs/endpoints and specific "methods" to invoke on those endpoints (RPC) - this adds coupling on the URL structure used. It also forces the client to know which method to call on what service - the server cannot change URLs and it cannot move a "method" from one service to another without breaking clients.
REST/hypermedia based systems behaves differently. In such a system the client and server agrees on one common entry URL where the client can lookup (GET) a service document, at runtime, describing all the possible interactions with the server using hypermedia controls such as links or forms. These hypermedia controls informs the client about how to interact with the service (the HTTP method and payload encoding) and where to interact with the service. Which in essence means we do not have "a service" anymore but possibly many different services as the client will be told, at runtime, where and how to interact with them.
So how does the client know which hypermedia controls it should look for? It does so by agreeing on a set of identifiers the server will use to identify the relevant controls. For links this is often referred to as "link relation types".
This leads us to what kind of "something" it is that servers and clients agree on - it is 1) a hypermedia enabled media type, 2) the root service index URL, 3) the hypermedia control identifiers and 4) the payload expected for each of the controls. At runtime the client then discovers the remaining URLs, HTTP methods and payload encoding (such as JSON, XML or URL-encoded key/value pairs).
Currently there are a small set of general purpose media types for hypermedia APIs - Mason, HAL, Sirene, Collection JSON, Hydra for JSON-LD and probably a few more.
If your are interested then I have covered this topic in various blog postings: