How do I get the permalink structure to work like this?

You can accomplish this with add_rewrite_rule().

I personally like to show this example in a class to make it copy/paste ready. You could throw this in a plugin or functions.php — some place that loads this code before query_vars, parse_request and init.

The goal is to add rewrite rules, make sure you can add custom properties to the main query, then replace the default template to be loaded with your custom template.

if (!class_exists('RentsAndCompaniesRewrite')):

    class RentsAndCompaniesRewrite
    {
        // WordPress hooks

        public function init()
        {
            add_filter('query_vars', array($this, 'add_query_vars'), 0);
            add_action('parse_request', array($this, 'sniff_requests'), 0);
            add_action('init', array($this, 'add_endpoint'), 0);
        }

        // Add public query vars

        public function add_query_vars($vars)
        {
            $vars[] = 'show_companies';
            $vars[] = 'show_rents';
            $vars[] = 'location';

            return $vars;
        }

        // Add API Endpoint

        public function add_endpoint()
        {
            add_rewrite_rule('^rents/([^/]*)/?', 'index.php?show_rents=1&location=$matches[1]', 'top');
            add_rewrite_rule('^companies/([^/]*)/?', 'index.php?show_companies=1&location=$matches[1]', 'top');

            flush_rewrite_rules(false); //// <---------- REMOVE THIS WHEN DONE TESTING
        }

        // Sniff Requests

        public function sniff_requests($wp_query) {
            global $wp;

            if ( isset( $wp->query_vars[ 'show_rents' ], $wp->query_vars[ 'location' ] ) ) {

                $this->handle_request_show_rents();

            } else if ( isset( $wp->query_vars[ 'show_companies' ], $wp->query_vars[ 'location' ] ) ) {

                $this->handle_request_show_companies();
            }
        }

        // Handle Requests

        protected function handle_request_show_rents()
        {
            add_filter('template_include', function ($original_template) {

                return get_stylesheet_directory() . '/templates/rents_by_location.php';
            });
        }

        protected function handle_request_show_companies()
        {
            add_filter('template_include', function ($original_template) {

                return get_stylesheet_directory() . '/templates/companies_by_location.php';
            });
        }
    }

    $wptept = new RentsAndCompaniesRewrite();
    $wptept->init();

endif; // RentsAndCompaniesRewrite

In a directory within your theme, add the templates you will use when the request is handled.

/templates/companies_by_location.php

<?php

global $wp;
$location = $wp->query_vars[ 'location' ];

echo 'Companies in the ' . $location . ' area:';

/templates/rents_by_location.php

<?php

global $wp;
$location = $wp->query_vars[ 'location' ];

echo 'Rents in the ' . $location . ' area:';