Remember, these are all just opinions.
The idea of randomly generated battlegrounds is great, but the generation is VERY bland. Add more hall and room shapes, sizes, and lengths. Add more statics (wall hangings, fallen rocks, etc.) to add to the barrels and tables. Add more monster types to each dungeon and, rather than sticking to 1-2 static levels, vary monster level across each dungeon, on each floor and between the floors. DEEPEN each dungeon both in feeling and physical (by physical I mean add more floors, for those that are tired <img src="/ubbthreads/images/graemlins/winkwink.gif" alt="" />). Randomize the look of the overworld and the merchant camp. Maybe even randomize the merchants themselves, in look, speech, and perhaps sheer number. Make the overworld FEEL random rather than 3 perfectly rhomboid landmasses and a triangle, or even make it into one landmass where monster migration from their designated spawn points can pose a challenge for an unweary player.
These are just some thoughts I had running through Act I BG.