Majority coloring for directed graphs
Let me answer Question 2. The answer is in negative: there exists an upper bound for majority coloring numbers of all tournaments. I will not care about the sharpness of the bound.
Let $G$ be a tournament on $n$ vertices, and let $d_1\leq d_2\leq \dots\leq d_n$ be the in-degrees of its vertices (denote the vertices $v_1,\dots,v_n$ respectively). We want to find its majority coloring in $3k$ colors.
Firstly, notice that the first $m$ vertices induce a sub-tournament with $m\choose 2$ edges. This means that $d_1+\dots+d_m\geq {m\choose 2}$, which yields $d_m\geq \frac{m-1}2$. Now we paint $v_1,\dots,v_{2k}$ with the last $2k$ colors; all the remaining vertices will be painted with the first $k$ colors, so the conditions for $v_1,\dots,v_{2k}$ are satisfied automatically.
Each of the remaining vertices has in-degree at least $k$. Consider a random coloring of them in $k$ colors. Now, for each $i>2k$, the probability $p_i$ that at least half of $\mathop{\rm In}(v_i)$ are painted with the color of $v_i$ can be bounded by Hoeffding's inequality as $$ p_i\leq \exp\left(-2\left(\frac12-\frac1k\right)^2 d_i\right)^2 \leq \exp\left(-\frac{(k-2)^2}{2k^2}(i-1)\right) $$ (the estimate may become even better if $\mathop{\rm In}(v_i)$ contains some of the first $2k$ vertices). So the probability that at least one vertex violates the required condition does not exceed $$ \sum_{i=2k+1}^n p_i \leq \sum_{i=2k+1}^n \exp\left(-\frac{(k-2)^2}{4k^2}(i-1)\right) <\sum_{j=2k}^\infty \exp\left(-\frac{(k-2)^2}{4k^2}j\right)\\ =\exp\left(-\frac{k(k-2)^2}{4k^2}\right)\cdot \left(1-\exp\left(-\frac{(k-2)^2}{4k^2}\right)\right)^{-1}. $$ This last bound tends to $0$ as $k\to\infty$, so it is less than $1$ for some value of $k$. This value fits.
Remarks. 1. One may try to improve this estimate by making something different with the vertices of low in-degree, e.g., introducing them into a general scheme and computing the sharp values of $p_i$ for these vertices. However, I doubt that a sharp bound may be obtained in this way.
- The estimates from the beginning do not work for arbitrary digraphs. However, we may see some conditions a hypothetical example should satisfy.
Firstly, a minimal example should not contain vertices of low total degree, since one may color the graph without such vertex, and then paint it with a color different from all its neighbors' colors. On the other hand, this graph should contain many vertices of relatively small in-degree, since otherwise the estimate using Hoeffding's inequality would work.
According to this link (see point $15$), Matt DeVos and David Wood can prove that every digraph in which each vertex has an out-neighbour has a good $4$-colouring (I am using their terminology).
Update. The paper Majority Colourings of Digraphs by Kreutzer, Oum, Seymour, van der Zypen (the OP), and Wood is now available on the arXiv. They give a short proof for $4$ colours and provide evidence for the conjecture with $3$ colours.
The paper mentioned above has been published:
Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood. "Majority Colourings of Digraphs" Electronic Journal of Combinatorics, 24(2):#P2.25, 2017. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p25
Other papers have appeared on this topic:
Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk. "Every digraph is majority 4-choosable" http://arxiv.org/abs/1608.06912
Fiachra Knox, Robert Šámal. "Linear Bound for Majority Colourings of Digraphs" https://arxiv.org/abs/1701.05715
A. Girao, T. Kittipassorn, and K. Popielarz. "Generalised majority colourings of digraphs" https://arxiv.org/abs/1701.03780