• Simulated Annealing is a nice trick that works very well for how simple it is (in it's basic form - it gets complicated when you make it fancy). It combines well with other tricks, since it's really more of a "framework-type algorithm" and not really a "mathy algorithm", so there are lots of "blanks" that you get to fill in. It's also attractive because it becomes arbitrarily good just by throwing more time at it - which means that on one side, you can make it quick if you don't really care that much about how good the answer is, or on the other side, you can make a very good answer just by waiting a long time. And it's the same code for both, so you can even make the speed a user input. That's a rare thing in algorithms.
• A* is a very often a good way to speed up an exhaustive search. It's like BFS, but instead of a queue it uses a priority queue, sorted by "distance from root + estimated distance to goal". What makes it particularly useful is that it's guaranteed to find the optimal answer when the estimated distance to the goal is never higher than the actual distance (heuristics satisfying this condition are called "admissible"). The maximum over a bunch of admissible heuristics is still admissible, so you can often make the search faster by making up more heuristics (unless evaluating the heuristics takes too much time, of course). If your heuristic is accidentally not admissible, that's one of the worst bugs to diagnose, so be careful.
  [I thought about putting A* in the list when I created the thread but had thought that too many people would already know it, but maybe not everyone does so here it is]

• Bloom Filters. I haven't really used them yet, but they look very useful when you want to do a quick but inaccurate test so you can save a large portion of slower but accurate tests - for example, google uses them in Chrome to pre-test a list of "dangerous" domains locally, so most queries don't have to go all the way to their servers.
• The Hungarian Algorithm finds a "best assignment" of "tasks" to "actors". This is an important optimization for real life, as well as in many programs, including games (for example if you have a bunch of units and a bunch of tasks in an RTS, and you'd like to not just pick the nearest the unit for each tasks greedily but calculate the optimal way to assign the tasks). It looks simple, but sadly it has steps that are difficult to do nicely on a computer.
• Interpolation Search is an adaptation of Binary Search that works extremely well when the items in the list are roughly uniformly distributed in their keyspace. Often neglected because it's not as "theoretically pretty" as basic Binary Search, but frequently a win in practice.

• Binary Decision Diagram solves all sorts of problems that you thought were hard or impossible, such as: boolean function equivalence, boolean satisfiability (and in fact the number of solutions, in time independent on the result) and Linear Boolean Programming. I've used BDDs with great success in many Project Euler problems (usually the "count solutions" part of BDDs) that were designed to require some mathematical insight. Great for "brute force - but smart".
• Zero Suppressed BDD's - a variation of BDDs especially suited to sparse functions, such as when solving some Exact Cover (or regular Set Cover) problems (not when choosing a set has very non-local results, such as with Sudoku) and you can actually get a count of solutions, pick a uniformly distributed random solution or a solution that optimizes the sum of weights of the chosen sets. Also good for representing all Hamiltonian paths though a graph, which you can use to solve some nontrivial instances or the Traveling Salesperson Problem.
• Dynamic Programming. Not an algorithm, but a class of algorithms so big that you have already used DP even if you didn't know it. For example, you know how to calculate Fibanacci numbers in linear time? That's DP. You've used Dijkstra's algorithm? DP. Learn about DP, it will come in handy. Maybe this shouldn't be on the list - almost everyone has heard about it.
• Branch and Bound. The wiki entry is just a stub, so no link. The idea is simple enough, but powerful: you do a Depth First Search, but you stop going down the recursion tree when the solution can not possibly become better by going down this sub-tree than the best solution found so far. Especially good when combined with a fast approximation. This technique can save your ass when it looks like you are going to have to use actual brute force, but when the cost function is monotonic while going down a sub-tree. Often applicable to solving puzzle games. It may seen niche, but I've had to use this in real life software that is actually used by people.
• Suffix Arrays, takes less space than a suffix tree, and useful for many of the same problems, such as many string problems (such as searching for substrings in sub-linear time). Other significant applications include a linear time Burrows–Wheeler transform (useful for data compression) and linear time Lempel Ziv decomposition (probably useful for LZ77/Deflate).
• Miller-Rabin primality test for when trial division gets too slow. It will test 64bit numbers for primality in mere miliseconds.
• Pollard's Rho algorithm for when trial division gets too slow and you actually need a factor, not just a boolean "IsPrime".

Exactly. I don't fully understand how you'd want high level languages improved. Full low-level access? Or implementations of everything you could do with those low-level things in the standard library? You'd still find missing things.