We examine two optimal leader selection problems for multi-agent networks, one defined in terms of controllability and the other in terms of robustness to noise. The optimal leader set in each problem is the set of m > 0 leaders that maximizes performance of a linear dynamic network. In the problem for controllability, each leader is identified with a control input, and performance is measured by average controllability and reachable subspace volume. In the problem for robustness, each leader responds to an external signal, the linear dynamics are noisy, and the performance is measured by the steady-state system error. Here we show that the optimal leader set for robustness maximizes a joint centrality of the leader set in the network graph and that the optimal leader set for controllability depends also on measures of the graph, including information centrality of leaders and eigenvectors of the graph Laplacian. Furthermore, we demonstrate that there is a fundamental tradeoff between optimal leader selection for controllability and for robustness.