Is detecting "doubly" arithmetic progressions 3SUM-hard?
This is an open problem.

Possibly some weak form of 3SUM-hardness could be proved by adapting a result from Mihai Pătrașcu's STOC 2010 paper "Towards Polynomial Lower Bounds for Dynamic Problems".  First, let me define a sequence of closely related problems.  The input to each problem is a sorted array $A[1..n]$ of distinct integers.


3SUM: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = A[k]$?
Convolution3SUM: Are there indices $i&lt;j$ such that $A[i] + A[j] = A[i+j]$?
Average: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = 2 A[k]$?
ConvolutionAverage: Are there indices $i&lt;j$ such that $A[i] + A[j] = 2A[(i+j)/2]$? (This is the problem you're asking about.)


In my PhD thesis, I proved that all four of these problems require $\Omega(n^2)$ time in a decision-tree model of computation that allows only queries of the form "Is $\alpha A[i] + \beta A[j] + \gamma A[k] + \delta$ positive, negative, or zero?", where $\alpha,\beta,\gamma,\delta$ are real numbers (that don't depend on the input).  In particular, any 3SUM algorithm in this model must ask the question "Is $A[i] + A[j]$ bigger, smaller, or equal to $A[k]$?" at least $\Omega(n^2)$ times.  That lower bound doesn't rule out subquadratic algorithms in a more general model of computation — indeed, it is possible to shave off some log factors in various integer RAM models.  But nobody knows what sort of more general model would help more significantly.

Using a careful hashing reduction, Pǎtrașcu proved that if 3SUM requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then Convolution3SUM requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time.  Thus, it's reasonable to say that Convolution3SUM is "weakly 3SUM-hard".  For example, if Convolution3SUM can be solved in $O(n^{1.8})$ time, then 3SUM can be solved in $O(n^{1.9})$ time.

I haven't ground through the details, but I'd bet that a parallel argument implies that if Average requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then ConvolutionAverage requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time.  In other words, ConvolutionAverage is "weakly Average-hard".

Unfortunately, it is not known whether Average is (even weakly) 3SUM-hard!  I suspect that Average is actually not 3SUM-hard, if only because the $\Omega(n^2)$ lower bound for Average is considerably harder to prove than the $\Omega(n^2)$ lower bound for 3SUM.



You also ask about the special case where adjacent array elements differ by less than some fixed integer $K$.  For 3SUM and Average, this variant can be solved in $O(n \log n)$ time using Fast Fourier transforms as follows.  (This observation is due to Raimund Seidel.)  

Build a bit vector $B[0..Kn]$, where $B[i]=1$ if and only if the integer $A[1]+i$ appears in the input array $A$.  Compute the convolution of $B$ with itself in $O(Kn\log Kn) = O(n\log n)$ time using FFTs.  The resulting array has a non-zero value in the $j$th position if and only if some pair of elements in $A$ sum to $2A[1] + j$.  Thus, we can extract a sorted list of sums $A[i]+A[j]$ from the convolution in $O(n)$ time.  From here, it's easy to solve Average or 3SUM in $O(n)$ time. 

But I don't know a similar trick for Convolution3SUM or ConvolutionAverage!