Warum sind dort Voltzahlen angegeben bzw. warum steht bei C4 16V, wenn der LM7805 doch 5V liefert (wahrscheinlich dumme Frage)?
Das ist die Spannungsfestigkeit der Kondensatoren, und da nimmt man eigentlich immer etwas mehr als theoretisch nötig, einfach um auf der sicheren Seite zu sein.

Bei C3 und C4 handelt es sich ja um ELKOs, bei denen die Polung wichtig ist. Bei C1 und C2 ist das anscheinend egal. Hat diese Wahl der unterschiedlichen Kondensatortypen irgendwelche Gründe?
Also zunächst mal haben Elkos natürlich eine erheblich höhere Kapazität als die meisten anderen Kondensatortypen, sie werden daher gerne als Pufferkondensatoren eingesetzt. C1 und C2 sollen den 7805 stabilisieren, da ist es sinnvoll kleine schnelle Keramik- oder Folienkondensatoren zu nutzen.

Warum haben C1 und C2 keine Spannungsangabe? Ist diese in diesem Fall nicht von Belang?
Weil diese, im Gegensatz zu Elkos, bei zu hoher Spannung normalerweise nicht explodieren