Hello Auge & Arnd!

What I'm just wondering: isn't <small> a non-semantic tag like <b> and <i>?

Yes it is.

No it isn't. (SCNR)
OK, to be serious, it depends on the context (do we assume that CSS is available or not). <u>, <strike>, and <s> are deprecated since HTML 4.01 strict.
The separation of content [(X)HTML)] and layout (CSS) is a wonderful thing, but mainly for the developer of the website. In most cases results of

<p><u>foo</u></p>

and

<p><span class="underline">foo</span></p>

plus

.underline { text-decoration:underline; }

or even worse

.underline { border-bottom:thin solid black; }

will look very similar at the client, but the HTML is simply larger.

A nice historical overview by Tim Tepaße at Jeena's Blog is based on his post in the SELFHTML-Forum in 2005. Great to read (sorry folks, German only).