You might want to google for "separating axis test", it is a very simple technique that allows you to detect collisions between any two convex polygons. It can also handle continous collisions detection for translation (your moving grenades) very easily.

In your axis-aligned case, you would project the objects you test on both axes (x and y). If the do not overlap on any one of the axes, they do not collide, otherwise they do. To handle movement you project each objects movement vector on the axes as well and add that to the objects projected interval.

To find out which grid squares that are covered by a polygon amounts to resterization, which you can find many tutorials for with google.

Axis aligned boxes are trivial to rasterize. For more complex shapes you write a rasterizer for triangles and handle arbitrary polygons by breaking them up into triangles (google "ear clipping").