If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?
A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though.

Tractability of convex problems essentially boils down to being able to decide if a solution $x$ is feasible, in a computationally tractable way (having a so called oracle available). There are convex sets for which this isn't the case. One such example if the set of co-positive matrices. If you are trying to find a matrix $M(x)$ such that $z^TM(x)z \geq 0$ for all $z\geq 0$, you have problems, as it is very hard to decide if a candidate $M(x)$ satisfies that property. Compare to the simple case of positive-semidefinite where all $z$ should lead to non-negativity, this is simply an eigenvalue test and thus semidefinite programming is tractable. Alas, also this statement is up for debate, as it depends on what you mean with solving a problem. A semidefinite programming problem with size $n$ (what ever we mean with that) can have a solution which whose representation grows at an exponential rate $2^n$.