45 gallons is pretty much minimum for an African Cichlid tank.
I'd agree that Pseudotropheus saulosi would work. Keep in mind that the males can be territorial, so I'd just have one in there.
Another option for you would be Yellow Labs (Labidochromis caeruleus). They are pretty well behaved and don't get too big. I've got a bunch in a tank with some Melanochromis cyaneorhabdos, which have been good tank mates (but in a 90 g) and the two look good together.
With any of the Malawi cichlids, if you over crowd them, you'll have less problem with territorial issues, but you'll have to be doing a lot of water-changes.