Typical use would be one of the following:
- "First of all," for the first point and "Second," for the second point.
- "First of all," for the first point and "Secondly," for the second point.
- "First," for the first point and "Second," for the second point.
- "Firstly," for the first point and "Secondly," for the second point. (Less common.)
So your analysis is pointing you in the correct direction. The next section explains this in some more detail.
"First of all," has emphasis and indicates the primacy of the first point, especially when there are more than two points. A one-syllable "First," can introduce the first point, but some find it too short to introduce a long concept of several points. The introduction "Firstly,", which is considered less formal, is sometimes used as a compromise when "First of all," is too strong but "First," seems understated.
Second, many people consider "Second," as a more correct or formal method to introduce the second point, but many people use "Secondly,". The phrase "Second of all," is logically incorrect: it would literally be the "second to all but the first", and in that regard, many consider it an egregious mistake. But it can be used for emphasis:
"Hey buddy, I didn't mean anything about it" said the stranger.
"First of all, I'm not your buddy," Fred started, "And second of all, if you insult my wife again, you're going to regret it!"
And finally, one could use "And finally," if it were actually the third-and-final point. Otherwise, one would use "Third,". The use of "Thirdly," starts showing the problem with the adverbial since "fourthly, fifthly, sixthly" are strange. Also, "Third of all," starts showing the self-defeating point of a continuous use of "X of all". An actual use of "Third of all," similar to the above "Second of all," would have to be quite emphatic, perhaps to the point of being shrill.
The fourth and final point might look like this. But rules are meant to be broken, and I can imagine a comedic use of emphasis in dialog using "And fourth of all,", perhaps ending with "And finally of all," :-)
And fifth, one might say this.
And my sixth and last point is that, unless its absolutely necessary, numbering one's points eventually becomes distracting.