Go for protein based phylogenetic information as these provide maximum information as you said yourself 20 amino acid as variables has much more information content versus 4 nucleotide. 

Difference varies from context to context, gene to gene, look in some example papers  on net, including some of my publications, good starting point will be Kumar, PeerJ (2015) at https://peerj.com/articles/1026/

As usual in science, it depends on the aim of your study. If you are trying to unveil the taxonomy of an unknown species, I would suggest you to work with 16S for bacteria/archea and 18S for eukaryotes.

If you are studying protein coding genes, as mentioned by Dr. Kumar, it might be more reliable to work with aminoacidic sequences (or translated nucleotidic sequences), as they have a higher information content ( 5x fold).

About the threshold of similarity in clustering sequences, it mostly based on experience on the sequences you are working with. It depends if you are working with nucleotides or coding sequences, the expected divergence between sequences, the evolutionary rate (K) of that region and the evolutionary distance between organisms that harbour the sequences. On top of that, there is also the aim of the study. It is not the same comparing variations among closely related populations (high similarity is expected) than variants between sequences that belong to different orders.

I would suggest you to read the books and reviews of Dr. Felsenstein, to learn the best approaches to your problem, as well as the most common pitfalls.

Cheers.

JMC

 Also start with 

Phylogenetic Trees Made Easy: A How-to Manual

Book by Barry G. Hall

Inferring phylogenies

Book by Joseph Felsenstein

Molecular Evolution and Phylogenetics

Book by Masatoshi Nei and Sudhir Kumar

Bioinformatics: Sequence and Genome Analysis

Book by David W. Mount