1. A method of authenticating a bitstream coupled to a programmable device to configure the programmable device, comprising: receiving the bitstream via a configuration port of the programmable device, the bitstream including configuration data for programming configuration memory of the programmable device, instructions for programming configuration registers of the programmable device, and at least one embedded message authentication code (MAC); storing at least a portion of the instructions received in the bitstream via the configuration port in a memory of the programmable device without programming the configuration registers; wherein the instructions include delay-sensitive instructions and delay-insensitive instructions, and the at least a portion of the instructions stored in the memory include only the delay-insensitive instructions; forwarding each delay-sensitive instruction to a configuration circuit for execution as such instruction is received in the bitstream at the programmable device; in response to receiving in the bitstream, a value that specifies a portion of the bitstream covered by one of the at least one embedded MAC that corresponds to the portion of the instructions, computing, at the programmable device, an actual MAC based on the bitstream using a hash algorithm; comparing the actual MAC with the one embedded MAC; in response to the actual MAC matching the one embedded MAC, forwarding the portion of the instructions from the memory to the configuration circuit for execution; executing each instruction stored in the memory to program the configuration registers; and programming the configuration memory with the configuration data from the bitstream based on executed ones of the instructions that program the configuration registers.