Determining if an integer appears more than $n/2$ times
You are asking two questions. I will only answer the second one. Consider the following set of possible inputs: the array is contains either $n/2$ or $n/2+1$ copies of $0$, all elements preceding it are $-1$, and all elements following it are $+1$.

I claim that any algorithm which works correctly for this set of inputs must query, in the YES instances, the first and the last position of the stretch of zeroes. Indeed, if it never queries the first position for example, then the input could have been the NO instance in which the value at that position is replaced by $-1$.

Since the first and last position of zero are at distance exactly $n/2$, and are the only two positions at that distance of equal value, we see that any correct algorithm for your problem can be modified (without any additional comparisons) to give an algorithm for the following problem:


  Given an array consisting of $n/2+1$ zeroes, preceded by $-1$ entries and followed by $1$ entries, find the location of the zeroes.


Since there are $n/2$ different answers to this problem, the usual decision tree argument shows that any comparison-based algorithm must make $\log_3 n - O(1)$ three-way comparisons, or $\log_2 n - O(1)$ two-way comparisons of the form "$x=y$ or $x \neq y$?". This shows that for two-way comparisons, your algorithm is nearly optimal. (Note that $2\log_4 n = \log_2 n $.)