I assume you are playing the old MacSoft version. Play the World and Conquests have a drop down menu for "Other Civs" at top left of the Diplo screen, but the old Vanilla version doesn't.
Put your mouse over one of the existing leaders in your Diplo circle.
Hold down Shift and Control, and click the mouse button.
You should see a menu appear up and to the left of your mouse. Select one of the leaders in that menu and it will replace the one you clicked.
Another way is to click the D button on the frame of the mini-screen at the bottom right corner of the map window. This should pop up a list of all known civs and you can chose to open the negotiation screen with one of them.
