Do new routes require a static first portion?
In the routing system you can't do this. What you can do is path aliasing.

Inbound: /{bar}/foo/{baz} -> /foo/{bar}/{baz}

Outbound: /foo/{bar}/{baz} -> /{bar}/foo/{baz}

You need a pattern to apply a regular expression on the path inbound, so /{bar}/{baz} is only possible if the parameters themselves have a distinctive pattern.

I didn't find a tutorial how to build a path processor, but you can use the 
PathProcessorFront class as example. 

Register both as tagged service in the .services.yml file for the module.

services:
  path_processor_front:
    class: Drupal\Core\PathProcessor\PathProcessorFront
    tags:
      - { name: path_processor_inbound, priority: 200 }
      - { name: path_processor_outbound, priority: 200 }
    arguments: ['@config.factory']