Sticking to a rectangular grid/mesh can be easy from the initial implementation point of view, but they aren't without their own problems. You have to consider the needs of your game to reach a good solution. If your game's actual play space is grid based then the rectangular grid solution should work quite well, but if you have a full 3D continuous game space, you'll probably find lots of potential problems with using a grid (How do you generate the grid? What resolution? How many nodes are necessary to get good coverage/accuracy?).
Going with a triangulated mesh isn't a clear win either. Given a 3D game, you could use some of the level geometry as a starting point for your triangulation, but you have to solve a lot of different problems (many of which don't have clear right answers/solutions) to get something that would be usable for your game. If you have the expertise and the capability, you can have the mesh and it will give you a lot of nice properties, but getting the mesh in the first place is often very difficult.
Check out Recast/Detour https://github.com/memononen/recastnavigation. It's a very nice (so I've heard, never used it myself, but the features look impressive) navigation mesh generation library and if I'm not mistaken, it was used in Killzone: Shadow Fall! The source is available so you can take a look at some of the techniques used.
If you're learning the basics of A*, pathfinding, and path following, I would highly recommend sticking to the rectangular grid as a starting point. If you do in fact have a 3D game, it probably won't be ideal but it's simple enough that it should get you going and have you focused on getting a complete workable solution for AI agents to reason about your world and path through it. Once you complete this, you could move on to having some sort of triangulated mesh. If so, I would recommend reading up on Delaunay triangulations and more specifically, constrained Delaunay triangulations.