GTA V was fun, but I’ve never been the biggest fan of the big city gangster setting in video games or movies, unless it’s about a cop fighting the drug dealers (like Max Payne). I prefer the outlaw setting of Red Dead. I expect another western from Rock Star in the future. Red Dead Redemption was too successful to just leave on the table.
Try playing Call of Juarez and Call of Juarez: Bound in Blood. They are nice linear shooters with great western storyline.