Okay, I actually posted in two other threads before the release how long it took to drive and fly between opposing corners in San Andreas and GTA IV. In Liberty City, driving took about 4 minutes and 30 seconds and flying took 1 minute and 5 seconds. In San Andreas (both using slower vehicles and getting lost on the country roads at one point and needing to stop the clock because I had no GPS to guide me), it took just under 6 minutes by driving and about 1 minute and 35 seconds flying the Hydra.
I'm waiting until I unlock the full map before I perform the tests in GTA V (both Los Santos alone and from one corner of the whole map to the other), but it's already much larger. Just from the impromptu guesstimating, it's taking me about as long to go from Sandy Shores to the hunting lodge up north (where you meet Cletus), which isn't even the northern border of the map, as it took to cross San Andreas by motorcycle.
Also, you probably just haven't FOUND the bums and serial killers in the woods. There's several dozen unique "random encounters" according to the progress section that you can access on your phone, which only activate when you approach a certain area. Think about how much space there is to look for random encounters like that.