I am a very good minesweeper player, and I can say that perfect play can get you to win in $99\%$ of the easy ($8\times 8$ with $10 $mines) or intermediate ($16 \times 16$ with $40$ mines) levels. In the expert level ($16 \times 30$ with $99$ mines) it becomes harder to win without making any guesses.
About first click not being a mine, this is obvious, since the mine positions should be generated after your first click, and I think this is the case in the known minesweeper games.
Although, perfect play is not enough, if the distribution of mines is completely random. For instance, I encountered many times the following configuration in a corner of the board
$\begin{matrix} \square& X & M \\ M & M & M \end{matrix}$, where $\square$ is free square, $M$ is a marked mine, and $X$ is an unknown mine. Imagine this configuration in the upper left corner of the table, and the counter says that there is only $1$ mine left. You would have to guess and have only $50\%$ chances of winning, since there is no clue as to where the mine is.
About implementing an algorithm of solving minesweeper games with perfect play, there are some things you should consider, since some of the mines are not always obvious to find. I have in mind a few steps when I solve minesweeper games:
If at one point, none of these steps can be applied, you can only guess the next step. Considering probabilities, is not very conclusive, since the values would be relatively close to $50\%$.
This is not a complete answer, but is too long for a comment (or perhaps even an answer!).
An analytical solution for the finite grid seems difficult. In such situations, either simulation and/or asymptotics can be helpful. Here I briefly sketch a little bit of both.
Monte Carlo Simulation
One way to get an estimate of the average number of revealed cells is to simulate a large number of games and look at what happens. Sometimes some simple analytical tricks can help along the way.
Below is an example heatmap showing the estimated average number of cells revealed at each position in the expert minesweeper board. Below that, I describe some details on how it was generated.
The cells are colored in a gradient from lowest (red) to highest (white) average number of cells revealed. This image was generated from averaging over 10 million random game instances. (Click on the image to see a larger version. For a version without the superimposed averages, click here.)
If you were to pick a cell randomly to play first, then the average number of cells revealed would be approximately 7.955. From this, it is clear that playing along the second band is quite suboptimal and on average you open up the board by two more cells by starting on the top or bottom row in the center.
Some details on the simulation
Note that if we are going to generate a random instances of the game, we might as well track how many cells on average are revealed at each position on the $16 \times 30$ grid. A simple, but slightly naive approach, is to generate random instances and keep track of the running total of cells that would be revealed by clicking on each of the starting positions.
However, we can immediately improve on this by recognizing a couple of key facts. First, we can use symmetry to reduce the variance. There are four different symmetry reflections of the board that must yield exactly the same averages. These are: (i) the original board, (ii) flipped along the vertical axis, (iii) flipped along the horizontal axis, and (iv) rotated 180 degrees. So, we can take our naive Monte Carlo and average over the four orientations to get an estimate that respects the symmetry and has lower variance.
Second, note that the individual cells partition nicely into equivalence classes. Cells that have mines or that are adjacent to mines form two separate classes. All other cells are clustered such that there is a closed border surrounding them formed by a combination of "mine" cells, "adjacent" cells and/or the board border. Each cell in a particular cluster will reveal the entire cluster when clicked and so each such cell reveals the same number of cells. This can be used to speed up the computation considerably.
Lest the behavior in the corners seems unintuitive, consider what happens when clicking on cell (1,1) versus (2,2). There is probability $p = 99/480$ in each case of the game immediately ending. Let $q = 1 - p$. Then, the probability of one cell being exposed is roughly $q-q^4$ in the first case and $q - q^9$ in the second. On the other hand, the probability of at least four cells being exposed is about $q^4$ for the (1,1) cell, whereas for the (2,2) cell, more than one cell being revealed occurs only with probability about $q^9$.
Asymptotics
As alluded to in the comments, this problem is closely related to the study of site percolation. In that context, we would consider the lattice $\mathbb{Z}^2$ with independent probability $p$ of each point of the lattice having a mine. We consider starting play by always uncovering the cell at the origin. We can ask the question of what the expected number of cells revealed will be, but we have to be careful since there may be positive probability of an infinite number of cells being revealed.
In site percolation models, it becomes more interesting to study the quantity $\theta(p)$, the probability that an infinite number of cells will be revealed. These problems are surprisingly challenging and rich mathematically. The book G. Grimmett (1999), Percolation, Springer, 2nd edition is a nice place to start.
In our case, it seems clear that an infinite cluster will contain the origin if and only if there does not exist any closed path surrounding the origin formed by $3 \times 3$ tiles that are adjacent (or touch at any corner) to one another, with a mine located at the center of each tile.
However, calculating that probability does not seem trivial, even using some standard percolation machinery.
Best Answer
We must ignore the "cannot lose on first click" rule as it severely complicates things.
In this answer, I will be using a notation similar to chess's FEN (Forsyth-Edwards Notation) to describe minesweeper boards. m is a mine and empty spaces are denoted by numbers. We start at the top of the board and move from left to right, returning to the left at the end of each row. To describe a specific square, the columns are numbered from a to h, left to right, and the rows are numbered from 8 to 1, top to bottom.
On a minesweeper board, all mines are adjacent to numbered squares that say how many mines are next to them (including diagonally). If there is ever a numbered square surrounded only by mines and other numbered squares, new squares will stop being revealed at that square. Therefore, the question is actually:
I like to approach problems like these by placing mines down one by one. There are 81 squares to place the first mine. If we place it in a corner, say a1, then the three diagonal squares adjacent to the corner (in this case a3, b2, and c1) are no longer valid (either a2 or b1 is now "trapped"). If we place it on any edge square except the eight squares adjacent to the corners, the squares two horizontal or vertical spaces away become invalid. On edge squares adjacent to the corners (say b1) three squares also become unavailable. On centre squares, either 4 or 3 squares become unavailable.
The problem is that invalid squares can be fixed at any time. For example, placing mines first on a1 and then c1 may be initially invalid, but a mine on b1 solves that.
This is my preliminary analysis. I conclude that there is no way to calculate this number of boards without brute force. However, anyone with sufficient karma is welcome to improve this answer.