The ultimate paladin sword is with Firkraag (Carsomyr +5). There are plenty of decent weapons (particularly the elven court longbow) that you can acquire by dishonourable methods from the golem room in the De Arnise Keep. To get Crom Faer +5/6 (I can't remember which), a truly excellent weapon, you need a Hammer of Thunderbolts +3 from the Mind Flayer lair in Baldur's Gate (IIRC, for this you need a key from Firkraag's lair someplace) and a scroll from the Shadow dragon. You also need, if I remember correctly, an item from the demons in the Underdark, which is not easy to get (I had to use Slayer change) together with another item (I think it's a girdle of Frost Giant strength and gauntlets of ogre power respectively) from somewhere. Take them all to Cromwell and you have something.

I second the Celestial Fury argument. Ironically, that fight was easy with a solo swashbuckler and hellishly tough with a full party.

The Staff of the Magi is a *really* hard fight in the bridge district. Take a look at any walkthrough for that area to find out how to get it. That said, it's also the most abusable item in the entire game, and still very powerful if used within the bounds of decency.