In doing research I've found that Alexander the Great made a ton of cities named after himself, but I'm wondering if these are the first cities to ever go by the name Alexandria or if there were any predating him.
There were not any Greek cities named Alexandria prior to Alexander the Great. Alexander learned this trick from his father, who founded Philippi in the mid-4th c. B.C.E. before his death. Alexander took a page from his fathers book and founded an Alexandria almost everywhere he went, the most well-known being the Alexandria of Egypt. Later Greek rulers, especially the Seleucids named cities after themselves (i.e.: Antioch) as well, following in Alexander's footsteps.