I agree that Paxos is much simpler than many people apparently think. It certainly didn't help that the original paper is almost completely useless for learning Paxos.

I highly recommend that anyone interesting in learning Paxos study this pseudo code from MIT's distributed systems class; it was the single thing that helped me understand Paxos most:

http://nil.csail.mit.edu/6.824/2015/notes/paxos-code.html