An deiner Stelle würde ich auf die Evaluationsboards verzichten.
Ich habe auch mit dem Pollin-Board angefangen, das Ding hat drei zwei LEDs, drei Taster und einen Summer-und das wars dann leider auch schon. Für die allerersten Schritte ist es ok...aber dafür sind 20€ zuviel Geld, finde ich.
An deiner Stelle würde ich mir was auf Lochraster zusammenlöten. Wenn man einigermaßen sauber arbeitet, ist das kein Problem.
Und dann würde ich dir die Tutorials auf mikrocontroller.net empfehlen. Da geht es erstmal mit einem ATMega8 los, und wenn du den programmieren kannst, dann kannst du alle AVRs programmieren.

Was du dir kaufen solltest, ist ein ISP-Programmer. Ich persönlich habe den Diamex All-AVR. Das Ding ist sehr brauchbar, läuft aber nur unter AVR-Studio 4. Mit AVR-Studio 5 hab ichs nicht hingekriegt, unter Version 6 soll es aber laufen-das hab ich allerdings nicht getestet.
Was ich dir ansonsten noch empfehlen würde wären eben Lochrasterkarten, eine Handvoll Wiederstände, Quarze und MKT/Keramikkondensatoren, ein paar Taster, LEDs, vllt auch ein LCD.
Wenn du dich entschliesst, mit Lochrastr zu arbeiten, würde ich dir noch raten 30€ in das Programm "Lochmaster" zu investieren.
Lochraster auf Papier vorzuzeichnen ist nervig, und bei etwas größeren Sachen sind Fehler vorprogrammiert, wenn man einfach draufloslötet.
Mehr braucht es meines Erachtens eigt nicht, um das Programmieren anzufangen.

Mit welcher Sprache du beginnen willst...das ist immer eine schlechte Frage, weil du keine einzige, richtige Antwort bekommen wirst. Sondern du wirst imemr nur die Antworten bekommen, die für den jeweiligen User richtig waren. Ich persönlich finde Assembler zum Lernen am Besten. Es erweitert das Verständnis zum Programmieren ungemein. Und es stimmt ehrlich gesagt auch nicht, dass Assembler sooooooooo schwer zu erlernen sei. Im Gegenteil. Es macht das Erlernen einer weiteren Sprache sogar sehr viel einfacher.
Meines Erachtens hat die meisten Vorteile der, der Assembler und C kann.


EDIT:
Wenn du Interesse hast, dann kann ich dir einen Bauplan für eine Software-Teststrecke auf Lochraster zukommen lassen. Diese Platine enthält ein paar Taster, einige LEDs, Potis und dieses 5-Euro-LCD von Pollin.
Einfach mal ne PN schreiben...