Trowell (who I haven't seen in awhile) put in randomize starting province feature into this online tool. Essentially takes the .map file and randomizes it a bit.
I love starting with an extra commander with possible, troops/items. For a thematic approach check out Xietor's epic hero mod. For a pure random standpoint on an individual map file check out trowell's site:
http://dominions.realites.org/
Doesn't always work (think it has to do with start, no start, blank) feature. But can be real fun. Looking forward to a mod version.
For feedback from doing this a bit, random items are cool and random troops are cool. Random fantastic starting commander is great, but having say 20 titans show up as troops kind of sucks. You just roll over anything. In the same vein, a free starting "commander" the standard 30g/17res guy kind of sucks too.
IMO I'd make an effort to reduce the amount of plain vanilla commanders while at the same time reducing the amount of crazy powerful troops. Limited items as well (I think random 4 was used a bit).
Just IMO.