1)
www.toheroes.com but mostly, MP maps
2) in TOH almost about 50% of the games r played ramdom maps, but personally, dont like it. U'll need Armaggedon's blade or Shadow of Death in order to have random senario generator.
3) IMHO, 3 is better than 4. Homm4 is still buggy, high sys. requirements(slow with my Athlon 1400 mhz), and somehow unfaithful to the HOMM series. But then, i only played 5 maps, and tried only 2 races. But homm4 has some very interesting stuff (magic system is similar to Magic the Gathering) and concept, but its not well executed like homm 2 and 3. U'll also hate the manual as well.
Finally, IMO the best maps r the ones that u make it (i have 2 homm3 maps that i spent 24 hours each).