What you should get really depends on the level of electronics knowledge that you have.
If you have zero or close to zero, go for the Uno. It is the best for a beginner as it will have the most community support, and the majority of add-ons/shields i have seen are based on using the Uno. added to that it is versatile and can still be used as you learn more.
If you have a little more experience, go the Mega. Don't quote me but I think it can still hold add-on boards, and has the advantage that it has extra IOs, whish is useful for bigger projects.
If you have a fair amount of experience, the nano can be good, as you can solder headers on it and just plug it into a breadboard and go from there.
As you learn more, you will find that your needs will change, and one board won't fulfil your needs.
As for the branding, it really shouldn't matter, but if you go a genuine arduino you should have less chance of there being any niggles or faults on the board.
Programming is the fun part, and will take a lot of reading to understand it. If you have questions, you would probably be best served asking in the Arduino forums.