The following parts of the Keep can be rebuilt by talking to Master Veedle. The order doesn't matter in most cases, as eventually you'll buy everything one way or another.
The Keep interior:
Captain's Suite (15 000)
Library (15 000)
West Wing (15 000)
Blacksmith (10 000)
Shop (10 000)
Wall repair (25 000)
Reinforcing the walls (50 000)
Building towers (75 000)
Widening the merchant trail (10 000)
Cobbling the trail (35 000)
Renovating other roads (50 000)
Adding bridges and towers (100 000)
In Act III there will be 2 new buildings to raise: the Church and the Tower. Here you'll have to decide how to use them, choosing between 2 possibilities for the church and 3 for the tower. The choice is mostly dependant on your liking, so don't expect to find any better and worse solutions.
Church -> Monk Order (50 000)
A shop with a few decent items and training for monk characters.
Church -> Temple of Tyr (50 000)
Some healing equipment to be bought here, as well as a shield that costs a whopping 250000 (and isn't really worth it). It's important to get this building if you're a paladin, because it will enable you to get the Holy Avenger. Check out the Mt Galardrym section of the guide for details.
Tower -> Neverwinter Nine's quarters (50 000)
A good shop for warriors and other physically-based characters.
Tower -> Mage's Tower (100 000)
A shop with lots of cool stuff for magic-based characters. You get the possibility of building it from talking to Startear who appears near the Keep gates a bit into Act III.