How can I properly set up dependencies in automated testing?

I think the main problem here is that you are loading WordPress’s bootstrap too early. Changing to this should fix it (I’ve interspersed comments explaining why things are in the order they are in):

// This file contains tests_add_filter(), so we need to load it
// so that we can hook the _manually_load_plugin() function to
// muplugins_loaded. We can't use add_action() because WordPress
// isn't loaded yet, and we can't load it quite yet (see below).
require_once $wp_tests_dir . '/includes/functions.php';

// This function loads the plugin and dependencies. We need to
// define it and hook it to muplugins_loaded before including 
// WordPress's bootstrap, since that will load WordPress. If
// we don't hook this up first, the hook will be fired when
// WordPress is loaded, and adding a hook to this after that
// will have no effect.
function _manually_load_plugin() {

     /* Code in here is probably the same. */
}
tests_add_filter( 'muplugins_loaded', '_manually_load_plugin' );

// Now that our function is hooked up, we can load WordPress, and
// the plugin and dependencies will be loaded when the hook gets
// called.
require_once $wp_tests_dir . '/includes/bootstrap.php';