Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time?
No, there is no linear time algorithm (for worst case).

Note for a list of $n$ positive integers, you can construct a tree with a root and $n$ children encoded by these integers respectively and traverse this tree in alphabetical order to sort these integers. So your problem is at least as hard as sorting.