I don't want to talk about interesting being a subjective quality but the main paradox.
Since the first dull number is interesting, we classify it as interesting. But then the second dull number becomes the first dull number. So it is also interesting.
But if we look again, we have two new members to the interesting category both of which are interesting due to being the first dull number. But two numbers can't be first, right? So what is going on? I want a better understanding of this paradox.

There's no a paradox at all! First of all we have to define what numbers would be "interesting". Then we may define that the rest of numbers are "dull".

But if we define that first "dull" number is "interesting" then we have to say that a set of "dull" numbers is empty.

You are effectively classifying any number as "interesting" if it has some property no other number has. But that immediately makes all numbers "interesting" because every natural number is 'unique'.

Hmm, I don't clearly understand this. I want to get a better understanding.
When we classify the first dull number as interesting, the second dull number becomes the first dull number. Hence we must classify it also as an interesting number. But here is the problem I don't understand - we just classified two numbers as interesting because both were 'first' which is not possible!

This does, however, have a useful logical error at its heart. The point is that "interesting" must be given a clear definition, in order to use it logically. So, you can decide whether a number is interesting or not.

To begin with let's assume that "being the smallest uninteresting number" is not one of the criteria.

So, you define some criteria to define interesting and find that, say, 1-13 are interesting and 14 fails the test and is dull.

Now, however, you add the criterion of being the lowest uninteresting number to the definition of interesting. But, this is now a new criterion to the definition of interesting that wasn't there at the start.

So, now you decide to add the criterion at the start. So, you say something like a number is interesting if:

1. It is prime
2. ...
3. It's the lowest uninteresting number

But this last criterion is not well-defined, as it requires a conclusion to be made (whether a number is interesting or not) before the definition is complete. This is the self-referential logical error with the process. You can't have a criterion that depends on the conclusion using that criterion.

This is actually quite interesting from mathematics point of view.

Of course, you could say that this proves there are no "dull" numbers, so every number is interesting. But we actually need to go a bit deeper.

There are a lot of "pseudo"-mathematical proves like this which yield contradictions. My favorite one is Berry's paradox. Take the least number x which cannot be defined by less than 1000 letters. But we have just defined x with less than 1000 letters, so there's a paradox.

What's the problem? Well, mathematically, we have not yet given a definition of what "defined" is, or what "interesting" is. Because we use vague terms like this, there are apparent contradictions. The resolution math takes is that everything must be defined rigorously in the form of well-formed formulas. In this instance, Berry's paradox, or the interesting number paradox do not show up.

David Wells' "The Penguin Dictionary of Curious and Interesting Numbers" lists 51 as the first uninteresting number. The first number not specifically listed is 58.