So I guess the 328 would be good as a starter?
Yes. I'd recommend you get a kit with the Duemilanove, like the one I showed you earlier.
What's the board between the Duemilanove and the blue breadboard?
That's a protoshield. I mentioned it earlier:
But the small breadboard is good for little projects, and if you plan on buying a Protoshield, it fits right on top.
Here's a link: