According to Midrash Sifri (Deuteronomy 343), Hashem first went around to all the nations and offered them the Torah before offering it to Bnei Yisroel. So why do we say in Kiddush and Birchas HaTorah that "Hashem Has Chosen Us From All of The Nations" when it would seem that we are the actually last option, and weren't initially chosen?
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.
My grand-grandfather, Rav P'sachya Lamm, ז״ל, asks why the mitzva of mila (circumcision) was given so much earlier than other mitzvos. He suggests as follows: Mila is for curbing our appetites. (He cites More N'vuchim for that.) The Sifre (beginning of B'racha) describes how other nations, on being offered the Torah, refused to give up their national heritages — licentiousness, murder, thievery. God wanted the Jews to accept the Torah (see Rashi to the start of B'reshis: the world was created bishvil Yisrael and the Torah), so he gave us the command of mila to prevent our base desires' getting in the way of our accepting the Torah (as the other nations' did). Ad kan tochen d'varav (end of the summary of what my great-grandfather wrote). According to this, I think it makes sense to say he "chose us".