The only province that is truly off your list would be Quebec, since you said that "most importantly speaking no french". New Brunswick has a high French population too, but most also speak English so, I would not cross that off your list.
There are good universities all across Canada, you just have to compare them and see what you are looking for in terms of your graduate or academic program that you are interested in. You can use the Maclean's Magazine Best Universities info to perhaps give you a comparison.
http://oncampus.macleans.ca/education/rankings/
The cities that have the highest cost of living (rent, food, etc) are Toronto, Vancouver, Montreal, Ottawa, and Calgary. Renting in areas around Fort McMurray and Edmonton are also expensive mainly because there are not enough homes to keep up with the demand. However, if you find that you like these cities, there is always the option to live in a suburb and commute or to look at apartments in parts of town that may not be as convenient or as modern.
Crime in Canada is not high. Here are violent crime statistics for some cities in Florida (rated per 100,000 people):
Jacksonville: 996
Tampa: 883
Miami: 1335
Here are how some typical cities in Canada compare:
Vancouver: 989
Hamilton: 776
Toronto: 709
Halifax: 1145
Surprisingly, the cities with the highest violent crime rate in Canada are not the ones most people would think. Saskatoon (SK) had the worst rate at 1612 per 100,000 people, and some other prairie towns did not fare too well. You can see a full list here:
http://www.cbc.ca/canada/story/2008/07/17/f-crime-2008.html
As for things to do, shopping and such, that pretty much depends on you. Obviously, I would say don't try to move to a town of 20,000 people and expect them to have parties every night, great bars, and loads of places to go. On the other hand, if you enjoy hiking, skiing, and other outdoor activities, downtown Vancouver or Toronto is probably not the place to be.
Good luck.