chords=>lead starting pitch?

For instance, "what's up" by 4 non blondes goes like this "A, Bm, D, A". Based on my scant experience with songs so far, I'd expect the song to start with A. But instead it starts in C# (according to my tuner)

C# is the major third of A.

I think he means if a song is in a certain key, then he expects that to be the first note of the song. So for that song example in the key of A, he's wondering why the first note is C# instead of A. Or am I missing the point?

The first note can be whatever note you want it to be. It would be very limiting to have to start every song with the same note. But I think being the tonic, it might be a good note to resolve on.

With the chords G, C, and D, Silent Night's in the key of G. So then you have the notes G,A,B,C,D,E,F#,G that you can work with, but not necessarily limit yourself to. Use whatever combination of notes you would like. As long as you are using these notes then you're in the key of G, with different combinations producing those different modes you've probably read about here.

I don't know the song in question, but...

An A chord contains 3 notes, A (root), C# (3rd) and E (5th).

Any of those notes in the melody fit the chord.  It is perfectly fine to start the melody with the 3rd of the chord.