I always liked Descartes' approach (if not his conclusions) of starting from the most essential, from the unshakably true, and then build from there. His most unshakable truth, which I believe stands to his day, is his 'I think therefore I am'. Then he went on to bring God into the picture in a really unwarranted way, but at least his starting approach was novel and important.

And so if we take his example and apply it a bit to some of the content of your post: it would be impossible to react negatively toward new information that clashes with our beliefs, if Aristotle's rules of logic were not true. I could say a thing, and then say the exact opposite, and no contradiction or cognitive dissonance would ever arise. Clearly that's not the case: we react negatively toward new information because we realize it falsifies our old views.

So we know opposites exist, just from that reasoning alone. In that way we can build solid bases on which to ground our thinking, and proceed from there. But few people care to lay the groundwork these days.