I agree that 512 is a good 'minimum' size. They are going to be small tiles though. Try it out at 256. If there is anything about it that displeases you or looks pixellated or funny, then submit the tiles at 512 and it will be fine.
Rounding the edges of the model you are baking from is a technical limitation of the baking process. They use this process on Gears of War and it looks great there. The rounding isn't that apparent on objects, especially when you get a very detailed model.
Very much agree on the bright colours. Duke is supposed to be grungy. If there is no detail on the tile, I personally would put some weathering on there or something that I think WOULD have been there if the resolution had been higher. Stuff like manufacturers marks, instruction and warning panels, screws and fasteners. Also, a lot of plastic surfaces have a patterned surface to hide scuffs and fingerprints.
The process I used with the pistol was to study some real guns and work out where there were switches, fasteners, grips, etc. and apply that detail where it would fit in with the old sprite.
I'd do specular maps, but I've got two other models going for Duke mods and I've got 3 other projects on the go at the same time, so I really can't take anything else on at the moment. I help out here and there where I can, but I can't do all the spec maps or all the other stuff I've promised to do already will get completely sidelined.
There are a number of workflows that kind of automate a lot of processes. Like you have a separate scratch layer, and you make it medium grey for the diffuse, white for the spec and black for the bump on the detail layer.
This is a great general tut for this kind of thing:
http://forums.cgsoci...ad.php?t=373024
He goes into technical techniques AND the thought processes behind where to put detail/grunge/wear.
When I've got one or two things out of the way, I'll do a complete 3D texture and demonstrate how its done for Duke, but honestly, tuts for this sort of thing are all over the net. There are a load of links in the tuts and resources thread.