Does there exist a data structure for quick list manipulation and order queries?
Keep your integers in skip lists. Normal skip lists are ordered by key, but we will just use them as a representation of sequences. Additionally, maintain an array of pointers of size $n$. Each element of the array should point to a node in a skip list. I believe this supports $next$ in $O(1)$ and all other operations in $O(\lg n)$.

Specifically:


$concat$ing or $split$ting two skip lists takes $O(\lg n)$ time and therefore invalidates at most $O(\lg n)$ pointers.
$next$ just follows the forward pointer at the leaf level, taking $O(1)$ time.
$first$ takes $O(\lg n)$ time: follow up pointers until you get stuck, then follow a left pointer. When you can't follow any more left pointers, you're at the head pointer of your skip list. Follow down pointers to the leaf, then one forward pointer. This is the first element in the list.
$follows$ is somewhat trickier. Proceed as in $first$ for $y$, but record a list of the values where you get stuck (that is, where you can't follow up pointers any more). We'll call this list you record a "trace". Do the same for $x$, but follow right pointers when you get stuck, not left. If $x$ precedes $y$, their traces will intersect. The traces are of size $O(\lg n)$. If each element in the trace is annotated with the stuck level, we can check for an intersection in time $O(\lg n)$.


$next$ is worst-case $O(1)$, all others are $O(\lg n)$ with high probability. They can be made worst-case by using deterministic skip lists.

I think $concat$ can be made $O(\lg \lg n)$ by using leaf-level-linked (2,5) trees and boostrapping the spines. For the bootstrapping trick, see "Purely functional representations of catenable sorted lists" by Kaplan and Tarjan.