How long can an octopus survive out of the water?
Short answer
Under ideal conditions, an octopus may survive several minutes on land.  

Background
Octopuses have gills and hence are dependent on water for the exchange of oxygen and carbon dioxide. Gills collapse on land because of the lack of buoyancy (source: UC Santa Barbara). Octopuses have three hearts. Two of these are dedicated to move blood to the animal’s gills, emphasizing the animal's dependence on its gills for oxygen supply. The third heart keeps circulation flowing to the organs. This organ heart actually stops beating when the octopus swims, explaining the species’ tendency to crawl rather than swim (source: Smithsonian).

According to the Scientific American, crawling out of the water is not uncommon for species of octopus that live in intertidal waters or near the shore (Fig. 1). Because most species of octopus are nocturnal, we humans just don't see it often. Their boneless bodies are seemingly unfit for moving out of water, but it is thought to be food-motivated, e.g. shellfish and snails that can be found in tidal pools. 

Octopuses depend on water to breathe, so in addition to being a cumbersome mode of transportation, the land crawl is also a gamble. When their skin stays moist, a limited amount of gas exchange can occur through passive diffusion. This allows the octopus to survive on land for short periods of time, because oxygen is absorbed through the skin, instead of the gills. In moist, coastal areas it is believed they can crawl on land for at least several minutes. Mostly they go from pool to pool, never staying out of the water for extended periods. If faced with a dry surface in the sun, they will not survive for long (source: Scientific American). 


Fig. 1. Octopus on land. Source: BBC

Your sub questions; I think small octopuses may survive longer, since passive gas exchange is the mode of survival on land. In general, an increase in diameter causes the volume to increase with a third power, while surface increases with a power of two. Therefore, an increase in body size reduces the surface-to-volume ratio and leads to reduced gas exchange. Because passive gas exchange needs large surface-to-volume ratios, I am inclined to believe small octopuses may cope better with terrestrial environments. However, in hot, arid conditions it is likely a bigger one will have an advantage, because it can store more oxygen in its blood. 

In terms of species, I have to say I couldn't find any sources going in so much detail on this. Likely, as said, smaller species may do better in cool, moist conditions, while larger specimens may be better off in dry environments.    

Reference
- Harmon Courage, Sci Am; (November 2011)