Yes, the co-domain of $f$ is meant to be $\mathbb{R}^n$. By concave, I mean that it is concave on each index: for any $\lambda \in [0, 1]$, $f(\lambda x + (1 - \lambda)y) \ge \lambda f(x) + (1 - \lambda) f(y)$ (the inequality is pointwise). I think the sublevel set is only necessarily path-connected if the domain of $f$ is $\mathbb{R}^n$, not $\mathbb{R}^n_{\ge 0}$.

I looked into it more - you're completely right, and now I'm trying to remember why I was so sure Simplex was strongly polynomial in the first place. I may have found one of the cases on which it's exponential. I found a source that says there are no known strongly-polynomial linear programming algorithms, and the existence of such an algorithm is a major open question. Thanks for your help!