How can CREATE OR REPLACE fail with already exists?
The OR REPLACE clause in CREATE FUNCTION is not meant for seamless parallel execution, it's meant to avoid dropping the function when we just want to update the body. From the doc:


  If you drop and then recreate a function, the new function is not the
  same entity as the old; you will have to drop existing rules, views,
  triggers, etc. that refer to the old function. Use CREATE OR REPLACE
  FUNCTION to change a function definition without breaking objects that
  refer to the function.


Now if several sessions issue the same CREATE OR REPLACE FUNCTION in parallel, there is indeed a potential race condition that is dealt with by relying on the unique index on (proname, proargtypes, pronamespace), and comes back to the caller as an error.

The error mentioned in the question happens if, for instance:


session #1 starts CREATE OR REPLACE and finds the function does not exist, so it creates it, inserting into pg_proc and locking the corresponding (proname, proargtypes, pronamespace) entry in the index.
session #2 starts CREATE OR REPLACE, finds the function does not exist (because #1 has not committed yet) and is put to wait for the index lock.
session #1 commits.
session #2 tries to insert and fails.


Note that not using explicit BEGIN/COMMIT does not change the race condition: the BEGIN/COMMIT pairs are just implicit around each SQL statement.

To have this parallel sequence work seamlessly, OR REPLACE would need to be to CREATE FUNCTION what ON CONFLICT is to INSERT, but that's not the case.

To deal with conflicting or identical DDL that might run in parallel, probably you should use an explicit lock at the beginning of the sequence to put it as a whole in a critical section. Advisory locks might be used for that. Or you need to implement a "retry on failure" strategy with savepoints around individual statements.