Let's perform a simulation experiment. We consider "the simplest bound" (denoted by $\rho_s$ below) the OP mentions, the bound arisen from Gershgorin's disc theorem (denoted by $\rho_g$ in the sequel; see the comment of Pavel Jiranek below the question body), and also the following bound which is obtained by considering the eigenvectors of $M$ (proof omitted):
$$
\rho_e(M)=\max\left\{ \max_j|b_j|,\ \frac{-(a_0+b) + \sqrt{(a_0-b)^2 + 4A}}2, \ \frac{(a_0+B) + \sqrt{(a_0-B)^2 + 4A}}2\right\},
$$
where $b=\min_j b_j,\ B=\max_j b_j$ and $A=\sum_{j\ge1}a_j^2$.
To measure how sharp the upper bounds are, for each selected value of $n$, we generate, 100,000 random matrices with $a_i$s and $b_j$s lying between $-1$ and $1$. For each random matrix, we calculate the ratio $\rho(M)/\rho_s(M)$. The maximum and mean of the 100,000 instances are then taken and these statistics are also computed for $\rho(M)/\rho_g(M)$ and $\rho(M)/\rho_e(M)$. The greater these ratios, the sharper the bound. Here are the results.
\begin{array}{c|ccc|ccc}
&&\text{max. }\frac{\rho(M)}{\rho_?(M)}&&&\text{mean } \frac{\rho(M)}{\rho_?(M)}\\
n&\text{simplest}&\text{Gershgorin}&\text{eigenvector}
&\text{simplest}&\text{Gershgorin}&\text{eigenvector}\\
\hline
2&0.9996&1.0000&1.0000&0.7837&0.8133&0.9311\\
4&0.9923&0.9998&1.0000&0.7549&0.6603&0.9018\\
8&0.9810&0.9389&0.9948&0.7654&0.4576&0.9009\\
16&0.9527&0.4600&0.9795&0.7974&0.3152&0.9160\\
32&0.9339&0.2803&0.9738&0.8355&0.2181&0.9342\\
64&0.9339&0.1802&0.9742&0.8718&0.1516&0.9507
\end{array}
From the above results, we see that while the bound from Gershgorin disc theorem performs fairly well for very small matrices ($n\le4$), its performance deteriorates very quickly when $n$ is getting large. In contrast, "the simplest bound" performs surprisingly well. It is worth notice that while the maximum ratio $\frac{\rho(M)}{\rho_s(M)}$ deterioriates slowly, the mean of $\frac{\rho(M)}{\rho_s(M)}$ actually increases with $n$. In other words, the average performance of $\rho_s$ is getting better and better for larger matrices. While it is interesting to see whether the performance of $\rho_s$ will surpass the performance of $\rho_e$ at some point, this simulation exercise is too time consuming and I will leave it to the readers to investigate.
