Where did Kaworu come from?

Kaworu was sent and apparently raised by SEELE. He believes that he is working together with them so that he can merge with Adam, as is the desire of all Angels. They have also made clones of him which are later used as the dummy plugs in the Evangelion Production Units.

Kaworu is not the first Angel to be under the control of an organization, as NERV has both Adam and Lilith. It is not clear exactly where SEELE got him from originally. It could be that they found him, or that he was created by them from some mixture of human and Angel DNA. The Red Cross Book, a program sold in theaters when the End of Evangelion was released, speculates that Kaworu may have been an Angel captured by SEELE when he was still an embryo.

Why does Kaworu tell Rei that he and she are "the same?"

There are a number of ways that Kaworu and Rei are the same. The one that Kaworu is probably referring to is that Rei is also at least partially constructed from Angel DNA and are in human form. That's far from the only link that they have with each other, though. They both have also been used by the organizations that have raised them - Kaworu by SEELE, Rei by NERV.

They also both have clones, if they are not clones themselves. At the time that Kaworu meets Rei, it is the third Rei clone. As for Kaworu, it is not clear whether he is a clone or an "original," but he definitely does have clones, as they are later used as the basis of the dummy plugs in the Evangelion production units (shown in Death & Rebirth and End of Evangelion). One other thing that they also have in common is the fact that they both love Shinji, although they definitely feel very different kinds of love for him.

One last, very important similarity between them is that Kaworu contains the soul of Adam and Rei presumably contains the soul of Lilith. This was not presented in the TV episodes or the movies, but was explained in the extended version of episode 24, which is available on the Japanese home video release, and the Red Cross Book, which was a program sold at screenings of the End of Evangelion movie in Japan. According to the extended episode 24, Kaworu contains the "salvaged soul" of Adam inside of him, while Ikari Gendo has Adam's body. In the Red Cross Book, Rei's is described as seemingly being derived from Lilith.
 

Why did Kaworu let Shinji kill him?

When Kaworu entered Terminal Dogma in NERV headquarters, he expected to find Adam there, as SEELE must have told him would be the case. All Angels have the overwhelming desire (or destiny, as Kaworu puts it) to return to Adam, even if it would mean the destruction of humanity. However, he realized that it was not Adam, but Lilith who was contained in Terminal Dogma.

Since he had no desire to return to Lilith, at this point he decided to sacrifice himself so that Shinji and the rest of humanity could survive. His survival would have meant the destruction of humanity because he would have continued in his quest to rejoin with Adam. To him, he explained, life and death were the same, so it did not really matter whether he lived or died.

It is unclear whether, at this point, he thought that Adam was within NERV headquarters or not, or what his actions would have been if he would have known that Adam was actually nearby. Whatever his knowledge was, at the point that he decided to let Shinji kill him, he was living up to his namesake, Tabris, the angel of free will. He made the choice to go against the "programming" that directed him to try to rejoin with Adam at any cost, and decided that the lives of Shinji and the rest of humanity were worth more than his life.

What's the big deal with Kaworu and Shinji calling each other by their first names when they first meet?

This one's fairly easy. First of all, let's clarify some terminology here. Let's call Kaworu and Shinji their given names (what we would usually call "first names," and Nagisa and Ikari their surnames (what we would usually call "last names.")

When they first meet, Shinji calls Kaworu by his family name, which is pretty usual in Japanese with someone that you don't know very well or at all. Well, Kaworu tells Shinji that he can call him Kaworu, his given name, which causes Shinji to blush and tell Kaworu that he can call him by his given name as well.

Well, calling people by their given names is clearly a more intimate level than calling them by their family names. It is usually reserved for people that you know a little better. However, this forwardness alone was probably not enough to make Shinji blush. Take a look at The Controversy for more thoughts on Shinji's blushing.