The Walker method (insert a pun about random walker) is possibly better known as the alias method. It's telling that the was it was initially described (and presented in the link you gave), its setup running time was n
(it requires sorting of the vector of probabilities). It was further improved by Kronmal and Peterson
to linear running time.
The algorithm is still very simple and elegant, but we can do a bit better under the original constraints of your puzzle. You initially asked for an algorithm with linear pre-processing and constant expected sampling time. The alias method gives constant worst case running time of the sampling procedure. The following is an even simpler method with trivial pre-processing and constant expected sampling time, where the constant is no more than 3.
Take the probability vector as it was given x1,...xn and line up the events on the line: y0=0,y1=x1,y2=x1+x2,...,yn=x1+...+xn=1. For a variable uniformly distributed between 0 and 1 the event [yi-1,yi] has probability xi.
Divide the line into bins on length 1/n. The claim is that each of the bins in expectation intersects with at most than three intervals [yi-1,yi]. Indeed, each bin which intersects with more than two intervals, fully contains all intervals except possibly for the leftmost and the rightmost one, of which there are at most n. This suggests the following trivial procedure: 1) Sample a real from [0,1] 2) Identify the bin it falls into 3) Using linear search in this bin, find its containing interval.
The algorithm can be implemented with two arrays of length n, of integers and reals, where the integer array contains the index j such that yj <= i/n < yj+1 (the first event which intersects with the bin) and the reals array contains yj+1-i/n for such j. Both arrays can be initialized in one pass through the array.
All in all, I think the above is simpler than even the binary search.