[al2o3cr]

    How about we use 24 bits of data pointers to keep the array size, or 1 bit to indicate "this is a pointer with a size" and 23 bits for the size

That would imply a pretty big granularity for the sizes - if the maximum size is 4GB, the minimum is 512 bytes. Packing more efficiently might help (for instance, the way segmentation limits on x86 are) but introduces hardware complexity.

    then our load/store with index instructions, as well as freshly added pointer arithmetic instructions, trap when the index exceeds the size?

You've described x86 segmentation pretty clearly here. It's been around since 1978, but most of the mechanism has been disabled in x86-64. Two of the registers involved are still used for things like per-CPU data and stack-smashing protection:

http://www.software-architect.net/blog/article/date/2015/03/...