Lots of opinions on this one - I've been carrying a small regular for several years now, very happily. Here's my thoughts:
Small vs. large is purely a matter of your needs. The small is a very classic size, and hangs very nicely in my pocket, so light and thin it's hardly noticable. I find the large a bit too... well, large for really comfortable EDC. It's also big enough to cross the line for legal folders many places, and a bit chunky and overbuilt for, say, opening plastic bags.
That said, if you don't mind the size, and have need of the larger blade, nothing wrong with the large.
Similarly, Classic style is nice, but I find the slightly more modern lines of the regular more attractive, and the geometry more to my liking. Purely personal preference, though.
I will say that I'd avoid a decorated Sebenza for your first Sebenza - I think of the decorated Sebenzas like I would if Peter Gransee started to decorate ARC's - it's OK, but not what I buy them for.
I find their customer service and support to be amazing - I've been very pleased, epecially with their free re-sharpening.