You'd be correct on both counts--I'd notate it as C major in 4/4 time, too. There's a strong swing feel throughout (with the occasional straight 16th notes, especially when the piece quotes the Underground theme). You might be notating the beat as too short, based on your words about phrase lengths--I'd notate the intro as 2 bars long. The phrases seem to have fairly clean lengths to me (often 4 bars long). Phrases sometimes do start with pickup notes, though.