Yes, you can omit the article.
Including the article and adding of all really just adds baggage without adding meaning.
There are occasions when the article really matters. There is a difference in meaning between saying:
He was most particular (about his clothes)
He was the most particular (dresser that we knew).
The first example merely defines the degree of his "particularity". The second compares him with all other dressers that the speaker knew.
But this distinction does not arise in your examples. In your second example, including of all is redundant. You have already specified of all at the start of the sentence. There is no point in repeating it at the end.