I vote sleeves because you can reuse them: if you tire of one fan card, you can make another!
Sitting down and sleeving thousands of cards isn't that bad, I've done it a few times. I find it easier to sleeve as you go, though. Like sleeve another kingdom each day, play a game with that kingdom, then the next day, pick 10 of the unsleeved ones (sleeve the randomizer cards to track it!). You don't have to do it this way, but it makes it less tedious. You get faster as you go pretty soon though.
The only downside to sleeves is the price, but I have no idea what custom stickers cost.