How to select correct SPI flash for specific micro-controller (pic32mx795f)?
How many bits.... if you're using an SPI Flash IC then the internal data width doesn't matter from your MCU's point of view.
How fast... read the appropriate section of the datasheet for your MCU; timing information for PIC I/O and peripherals is in the technical specs near the end of the document.
Should I consider other interfaces... depends on your requirements; for most non-volatile memory requirements, SPI is perfectly adequate and it has many advantages (small physical size and minimal usage of MCU I/O pins are key examples).