For more sf/fantasy,
Book View Café,
Small Beer Press, and
Mundania Press all take Paypal.
Both Small Beer and Mundania have most of their catalogues available via Fictionwise as well, and may be cheaper there with coupons (but also offer their own discounts on special occasions). Book View Café also has some of their stuff up at Smashwords, and sometimes participate in Smashwords sales.
For romance,
All Romance eBooks' FAQ says it takes Paypal. They've also got a more general stock store,
Omnilit, but frankly most of their catalogue and sale deals are for romance books.
One warning about paying via Paypal at Baen. If you want to gift your Webscription monthly bundle purchase (they let you send a coupon to someone else for a free copy), you'll have to pay via credit card. It has something to do with Baen being able to confirm that the money's really going to be there which apparently doesn't happen with Paypal purchases.
Hope this helps.