In the Vilna Gaon's commentary to a story in the Gemara (Bechoros 8b) about a debate between R' Yehoshua and the "Sages of Athens" (this commentary has been adapted into English, in The Juggler and the King, by R' Aharon Feldman), he explains that Hashem's reason for offering the Torah first to the nations was indeed to demonstrate that it doesn't "fit" with them, and that it is suitable only for the Jewish People, the most refined of nations. In short, then, Hashem's offer itself further underscored our uniqueness and chosenness.
That said, your question presupposes only one level of choice - granted, the one we're most familiar with. But there are actually higher levels of choice too, and those are also included when we speak of Hashem having chosen us. This article gives an overview of this idea based on Chassidic ideas in general, and the teachings of the Lubavitcher Rebbe zt"l in particular. Two key paragraphs:
The ultimate definition of choice is
that it is the free and uninhibited
expression of the chooser's
quintessential self. So it is with
G-d: if He chose, His choice reflects
His singular reality. If He chose,
His choice is absolute and
unequivocal, not an arbitrary
selection out of several
possibilities. If He chose us, then it
is ultimately a choice that is rooted
in His very essence.
The two lower dimensions of choice are
also valid descriptions of G-d's
choice of Israel. But they are only
part of the story -- the part that
pertains to the level of reality on
which they are effected. So when the
Jew is chosen because of his virtues,
it is a reasoned choice, but it is
also much more than that; when the lot
falls on Jacob it is a supra-rational,
arbitrary choice, but it is also much
more then that: ultimately, these are
but outward expressions of the
ultimate choice that is intrinsic to
the divine essence.