An algorithm that may approximate your requirements is to divide the dataset into buckets of 10 equal ranges. Then sort each bucket and select the 'best' from each group.

To approximate my reading of your criteria, I've sorted the pairs in each group by it's distance from the group median divided by it's weight (quality). This tends to favour quality over distance. I also tried the square of the distance divided by the weight, which tends to strongly favour proximity to the median, over quality. The sort can be easily adjusted to produce the results that best suit your purpose.

It handles 1e4 in < 1 sec; 1e5 in ~5 secs; 5e5 in ~38 secs; & 1e6 in ~ 97 secs; which is close enough for me to consider the implementation as O(n) in terms of time. It will vary with ratio of data to selections to some degree, though as the number of selections grow, the individual sorts are smaller, which tends to compensate. It might benefit from a more efficient sort than the ST I've used.

#! perl -slw
use strict;
use Data::Dumper;
use List::Util qw[ reduce first ];

our $N ||= 100;
our $MIN ||= 10;

my @data = sort{
    $a->[ 0 ] <=> $b->[ 0 ]
} map{
    [ rand 1000, 1+ int rand 9 ]
} 1 .. $N;
#print Dumper \@data;

my $min = reduce{ $a->[0] < $b->[ 0 ] ? $a : $b } @data;
my $max = reduce{ $a->[0] > $b->[ 0 ] ? $a : $b } @data;
my $gap = ( $max->[ 0 ] - $min->[ 0 ] ) / $MIN ;
#print "$min->[0]:$max->[0]:$gap";

my @buckets;
push @{ $buckets[
    ( $data[ $_ ][ 0 ] - $min->[ 0 ] -1 ) / $gap
] }, $data[ $_ ] for 0 .. $#data;
#print Dumper \@buckets;

my @selected;
for my $bucket ( 0 .. $#buckets ) {
    my $mid = (( $bucket+1 ) * $gap ) - ( $gap / 2 ) + $min->[ 0 ];
    $selected[ $bucket ] = (
        map{
            $_->[ 1 ]
        } sort {
            $a->[ 0 ] <=> $b->[ 0 ]
        } map {
           [ abs( $_->[ 0 ] - $mid ) / ( $_->[ 1 ]||1 ), $_ ]
        } @{ $buckets[ $bucket ] }
    )[ 0 ];
}

my $next = 0;
my $group = $min->[ 0 ];
printf "\nGroup: %f - %f; median: %f\n",
    $group, $group + $gap, $group + ( $gap / 2 );
$group += $gap;

for my $idx ( 0 .. $#data ) {
    if( $data[ $idx ][ 0 ] > $group ) {
        printf "\nGroup: %f - %f; median: %f\n",
            $group, $group + $gap, $group + ( $gap / 2 );
        $group += $gap;
    }
    my $selected = ' ';
    if( $next < @selected and $data[ $idx ][ 0 ] == $selected[ $next ]
+[ 0 ] ) {
        $selected = $next;
        ++$next;
    }
    printf "%1s\t[ @{ $data[ $idx ] } ]\n", $selected;
}
[download]