How to get relative URL of medium sized featured image?

You’re on the right track with your first snippet – from there it’s easy to remove parts of the url: check what WP has stored as the site root, then use php’s string functions to snip that part out of your image url.

// inside the post loop, in a template file
if ( has_post_thumbnail()) {
  $medium_image_url = wp_get_attachment_image_src( get_post_thumbnail_id($post->ID), 'medium');
  $domain = get_site_url(); // returns something like http://domain.com
  $relative_url = str_replace( $domain, '', $medium_image_url[0] );
  echo $relative_url;
}

If you wanted this to exist as a reusable function:

// functions.php
function get_relative_thumb( $size ) {
   global $post;
   if ( has_post_thumbnail()) {
     $absolute_url = wp_get_attachment_image_src( get_post_thumbnail_id($post->ID), $size);
    $domain = get_site_url(); // returns something like http://domain.com
    $relative_url = str_replace( $domain, '', $absolute_url[0] );
    return $relative_url;
   }
}

// in a template file
<?php 
      while (have_posts) : the_post();

      // ... post loop content before the thumbnail

      echo get_relative_thumb( 'medium' ); 

      // ... post loop content after the thumbnail

      endwhile;
?>

(Note – the result from this will likely still include the ‘wp-content/’ part of the path; if you need to remove that so it just starts at ‘upload’, just append ‘wp-content’ to the $domain variable before you run str_replace. (If this is intended for general release, you should use wordpress’ built-in functions to get the path programatically, in case someone isn’t using the typical ‘wp-content’ directory structure.)