kay. so when you get the message diablo walks the earth, he doesn't exist anywhere yet. go to any superunique boss monster and he'll spawn there (i forgot if you have to kill the superunique or not, doesn't really matter they're kinda weak. =o). some popular places are eldritch (since theres a wp nearby), corpsefire, bishbosh, raikinshu, or treehead (since they're all in a1 and the monsters are easy).
I like to spawn him in the Den of Evil, as the structure of the place prevents him from moving around too much, and also provides easy cover for his fire attacks (should you need it).
A note, for him to spawn in a specific place, you cannot have visited the area before in the same game. This because he spawns instead of the superunique so if the superunique already has been spawned by you, Uber cannot spawn there.